题意
给定一个\(n\)个点\(m\)条边的无向图，有一些边权暂时为\(0\)，你需要分配一个\([1, 10^{18}]\)的数。最终使得\(s\)到\(t\)最短路为\(L\)，输出一个可行的分配方案，或告知无解。
\(n \leq 10^3\)，\(m \leq 10^4\)，\(L \leq 10^9\)
题解
首先拿到这个图，我们把\(0\)边换成INF，求\(s\)到\(t\)的最短路\(d\)，如果此时\(d<L\)，则无解
再把\(0\)边换成\(1\)，求最短路\(d\)，如果\(d>L\)，也无解
上面两行是显然的，我们现在证明除了以上情况，一定有解。
考虑把\(0\)边换\(1\)。然后所有\(s\)到\(t\)的路径拿出来按权值从小到大排序，这时第一条路径\(d\leq L\)。若\(d=L\)则结束，否则这条路径一定含有可变边。把可变边+1（这可能导致一些路径权值+1）。重复上述过程就能得到解。
那么第一种做法：我们用和证明相似的做法来求解。把\(0\)边换\(1\)后，我们找一条任意最短路径。我们之间把不在这路径上的可变边变成INF并固定，不需要考虑。这样一定是对的。不经过可变边的路径>L，经过非标记可变边的路径=inf，只剩下经过标记边的路径要考虑。
那么我们每次跑一下最短路，找到最短路上一个标记边，然后改成\(L-d\)并固定。这样进行若干次一定能出解。容易看出最多n次（标记边数量是\(O(n)\)的），这个复杂度
「CF716D」Complete The Graph「最短路」
原文：https://www.cnblogs.com/hongzy/p/11514912.html