传送门：>Here<
题意：给出一张带权无向图，其中有一些边权为0。要求将边权为0的边的边权重置为一个任意的正整数，使得从S到T的最短路为L。判断是否存在这种方案，如果存在输出任意一种
解题思路
注意是最短路是L，而非存在一条路径为L。并且边权为0的边必须变为正整数，最小也得是1
这题由于n=1000，所以可以稍微暴力一点……
首先，先不加任何一条为0的边跑Dij，如果此时的最短路已经$< L$，那么后面的边无论怎么加都不会使最短路比当前的大了，因此无解
此时最短路$geq L$。然后考虑一条一条把边加进图里。每一条塞进图里的边权值都设为最小（也就是1）。如果加上了当前这条边使得最短路$< L$了，那么导致最短路变小的一定就是当前这一条边。因为除了通过当前这条边的路径以外其他路径都$geq L$。所以我们可以修改这一条边的权值为$L-d[t]+1$，也就是把最短路凑成等于L。并且修改之后所有的路径依然$geq L$。如果加上当前这一条边最短路依然$geq L$，那么这条边就是废掉的，可以不管。所以我们需要做的，就是对于每一条使最短路$< L$的边都做此修改。最后判断最短路是否等于L即可。复杂度$O(m^2 log n)$，非常巧妙~
Code
注意应当把无法使路径变小的边权值设为1
/*By DennyQi*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #define r read() #define Max(a,b) (((a)>(b)) ? (a) : (b)) #define Min(a,b) (((a)<(b)) ? (a) : (b)) #define ERR {puts("NO");return 0;} using namespace std; typedef long long ll; #define int long long const int MAXN = 3010; const int MAXM = 30010; const int INF = 1e13; inline int read(){ int x = 0; int w = 1; register int c = getchar(); while(c ^ '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c >= '0' && c <= '9') x = (x << 3) +(x << 1) + c - '0', c = getchar(); return x * w; } struct Edge{ int u,v,w; }a[MAXM]; struct Node{ int idx,w; }; inline bool operator < (const Node& a, const Node& b){ return a.w > b.w; } int N,M,L,S,T,x,y,z; int first[MAXM*2],nxt[MAXM*2],to[MAXM*2],cost[MAXM*2],num_edge; priority_queue <Node> q; int d[MAXN],vis[MAXN]; inline void add(int u, int v, int w){ to[++num_edge] = v; cost[num_edge] = w; nxt[num_edge] = first[u]; first[u] = num_edge; } inline void Dijkstra(int s){ for(int i = 0; i <= N; ++i) d[i] = INF; memset(vis, 0, sizeof(vis)); d[s] = 0; q.push((Node){s, 0}); int u, v; while(!q.empty()){ u = q.top().idx; q.pop(); if(vis[u]) continue; vis[u]=1; for(int i = first[u]; i; i = nxt[i]){ v = to[i]; if(d[u] + cost[i] < d[v]){ d[v] = d[u] + cost[i]; q.push((Node){v,d[v]}); } } } } main(){ // freopen(".in","r",stdin); N=r,M=r,L=r,S=r,T=r; for(int i = 1; i <= M; ++i){ a[i].u=r, a[i].v=r, a[i].w=r; if(a[i].w != 0){ add(a[i].u,a[i].v,a[i].w); add(a[i].v,a[i].u,a[i].w); } } Dijkstra(S); if(d[T] < L) ERR; for(int i = 1; i <= M; ++i){ if(a[i].w != 0) continue; a[i].w = 1; add(a[i].u,a[i].v,1); add(a[i].v,a[i].u,1); Dijkstra(S); if(d[T] < L){ a[i].w = 1 - d[T] + L; cost[num_edge-1] = 1 - d[T] + L; cost[num_edge] = 1 - d[T] + L; } } /* for(int i = 1; i <= M; ++i){ printf("%d %d %d ", a[i].u,a[i].v,a[i].w); } printf("d[%d] = %d ",T,d[T]);*/ Dijkstra(S); if(d[T] != L) ERR; puts("YES"); for(int i = 1; i <= M; ++i){ printf("%lld %lld %lld ", a[i].u,a[i].v,a[i].w); } return 0; }