P10178 陌路寻诗礼

最短路 广度优先搜索

题目大意

给定一个 $n$ 个点 $m$ 条边的有向图，对于每一条边都可以赋 $[1,k]$ 范围内的权值，请问怎样赋值才能使 $1$ 到任意点的最短路径都是唯一的？

思路

首先，我们可以假设所有的边权都是 $1$，然后开始跑 dijkstra。如果每一条最短路径都是唯一的，那么最后的边权都赋为 $1$ 就行了。但要是不唯一呢？

很简单，因为 dijkstra 是根据向上的拓扑序来求解的，第一次遇到的点一定是最优的。如果我们发现后面的跟前面一样优，我们就在边权上面加上 $1$，这样子这条路径就不是最优的了。

最后我们判断如果有边权超过了 $k$，那么就代表无解，否则输出即可。注意这题虽然答案有可能边权有不为 $1$ 的，但是在求解的过程中每一条边只会遍历一次，而且额外增加了权值的边也不可能成为最短路径的一部分，所以不需要使用优先队列，只需要使用普通的队列即可。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
const int kMaxN = 3e5 + 5;
 
struct Edge {
  int to, id;
};
 
int d[kMaxN], f[kMaxN], a[kMaxN], t, n, m, k;
vector<Edge> e[kMaxN];
queue<int> q;
 
bool dijkstra(int s) {
  fill(a + 1, a + m + 1, 1);
  fill(d + 1, d + n + 1, 1e9);
  fill(f + 1, f + n + 1, 0);
  for (q.push(s), d[s] = 0; q.size(); q.pop()) {
    auto t = q.front();
    if (f[t]) {
      continue;
    }
    f[t] = 1;
    for (auto i : e[t]) {
      if (d[t] + 1 < d[i.to]) {
        d[i.to] = d[t] + 1;
        q.push(i.to);
      } else if (d[t] + 1 == d[i.to]){
        a[i.id]++;
      }
    }
  }
  return *max_element(a + 1, a + m + 1) <= k;
}
 
int main() {
  for (cin >> t; t; t--) {
    cin >> n >> m >> k;
    fill(e + 1, e + n + 1, vector<Edge>());
    for (int i = 1, u, v; i <= m; i++) {
      cin >> u >> v;
      e[u].push_back({v, i});
    }
    if (dijkstra(1)) {
      cout << "Yes\n";
      for (int i = 1; i <= m; i++) {
        cout << a[i] << (i == m ? '\n' : ' ');
      }
    } else {
      cout << "No\n";
    }
  }
  return 0;
}