#最短路 #广度优先搜索
## 题目大意
给定一个 $n$ 个点 $m$ 条边的有向图，对于每一条边都可以赋 $[1,k]$ 范围内的权值，请问怎样赋值才能使 $1$ 到任意点的最短路径都是唯一的？
## 思路
首先，我们可以假设所有的边权都是 $1$，然后开始跑 dijkstra。如果每一条最短路径都是唯一的，那么最后的边权都赋为 $1$ 就行了。但要是不唯一呢？
很简单，因为 dijkstra 是根据向上的拓扑序来求解的，第一次遇到的点一定是最优的。如果我们发现后面的跟前面一样优，我们就在边权上面加上 $1$，这样子这条路径就不是最优的了。
最后我们判断如果有边权超过了 $k$，那么就代表无解，否则输出即可。注意这题虽然答案有可能边权有不为 $1$ 的，但是在求解的过程中每一条边只会遍历一次，而且额外增加了权值的边也不可能成为最短路径的一部分，所以不需要使用优先队列，只需要使用普通的队列即可。
## 代码
```cpp
#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;
}
```
```