【图论思维】cf715B. Complete The Graph加强

题目大意

【图论思维】cf715B. Complete The Graph加强-LMLPHP

有一张$n$个点$m$条边的简单正权无向图，$S$到$T$的最短路为$L$，现在有一些边的边权未知，请输出任意一种满足题意的方案。

$n,m\le 500000$.

题目分析

首先对于每一条边权未定的边，把它的边权设为1，处理出$dist_i$表示在这种情况下，$T$到$i$的最短路距离。之后再从$S$开始做dij，设$S$到$u$的最短路为$len_i$，那么当前若以$u$为起点增广一条边权未定的边$(u,v)$，就将其边权设为$\max\{1,L-len_u-dist_v\}$。最后若$T$的最短路不为$L$则无解。

关于第二次重设边权，如上处理之后在有解情况下显然第二次dij出的$len_i \le L$，那么剩下的就是考虑：可不可能把一条$L$的最短路给刷得更小了。

分步地看这个问题，我们最后一次进行重设边权操作时，等于说是钦定了一条过这个边的长度为$L$的路径（因为$len_i$是依靠重新设的边权做的最短路），也就是说一定是满足条件的最短路。反之如果这个做法无解，说明任意的未定边权的边都不在长为$L$的最短路上，那么也就没有任何影响。

注意如果（像我一样偷懒不刷完全图）那么需要判一判未经过的边。

时间复杂度：$O(n\log n)$

 #include<bits/stdc++.h>

 typedef long long ll;

 const int maxn = ;

 const int maxm = ;

 const ll INF = 1000000000000000000ll;

 struct Edge

 {

     int v;

     ll val;

     Edge(int a=, int b=):v(a),val(b) {}

 }edges[maxm];

 struct node

 {

     int x;

     ll d;

     node(int a=, ll b=):x(a),d(b) {}

     bool operator < (node a) const

     {

         return d > a.d;

     }

 };

 int n,m,L,S,T;

 int edgeTot,head[maxn],nxt[maxm];

 ll dis[maxn],len[maxn];

 int dfn[maxn],tim;

 std::priority_queue<node> q;

 int read()

 {

     char ch = getchar();

     int num = , fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = -;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     return num*fl;

 }

 void addedge()

 {

     int u = read()+, v = read()+, c = read();

     edges[edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot, ++edgeTot;

     edges[edgeTot] = Edge(u, c), nxt[edgeTot] = head[v], head[v] = edgeTot, ++edgeTot;

 }

 int main()

 {

     memset(head, -, sizeof head);

     n = read(), m = read(), L = read(), S = read()+, T = read()+;

     for (int i=; i<=m; i++) addedge();

     memset(dis, 0x3f3f3f3f, sizeof dis);

     tim = , q.push(node(T, )), dis[T] = ;

     for (int tmp; q.size(); )

     {

         tmp = q.top().x, q.pop();

         if (dfn[tmp]==tim) continue;

         dfn[tmp] = tim;

         for (int i=head[tmp]; i!=-; i=nxt[i])

         {

             int v = edges[i].v, c = edges[i].val?edges[i].val:;

             if (dis[v] > dis[tmp]+c) dis[v] = dis[tmp]+c, q.push(node(v, dis[v]));

         }

     }

     memset(len, 0x3f3f3f3f, sizeof len);

     tim = , q.push(node(S, )), len[S] = ;

     for (int tmp; q.size(); )

     {

         tmp = q.top().x, q.pop();

         if (dfn[tmp]==tim) continue;

         dfn[tmp] = tim;

         if (tmp==T){

             if (len[T]!=L) puts("NO");

             else{

                 puts("YES");

                 for (int i=; i<=n; i++)

                     for (int j=head[i]; j!=-; j=nxt[j])

                         if (edges[j].v > i) printf("%d %d %lld\n",i-,edges[j].v-,edges[j].val?edges[j].val:INF);

             }

             return ;

         }

         for (int i=head[tmp]; i!=-; i=nxt[i])

         {

             if (!edges[i].val){

                 edges[i].val = edges[i^].val = std::max(L-len[tmp]-dis[edges[i].v], 1ll);

             }

             int v = edges[i].v, c = edges[i].val;

             if (len[v] > len[tmp]+c) len[v] = len[tmp]+c, q.push(node(v, len[v]));

         }

     }

     puts("NO");

     return ;

 }

END

dij