B. Complete The Graph(最短路算法)

题目链接

　　这个题目的题意是在最短路上是否可以满足边权之和等于给定的L；因此我们可以先不加边权为0的点用dijsktra算出最短路，判断是否可以满足

（1）如果满足，将边权为0的边初始化为无穷大（防止影响当前的1最短路），就是当前的答案；

（2）如果小于的话说明不存在，因为此时为0（可修改的点的边权）并未加入，此时说明在不加这些边的情况下存在最短路，因此这个值不可能满足

（3）大于的话，说明没有最短路，因此我们将边权为0的边一条条的加入，知道加入一条边后小于（说明有最短路了）或等于（恰好满足）L；

  1 #include<iostream>
  2 #include<cstring>
  3 #include<vector>
  4 #include <queue>
  5 #include<string>
  6 using namespace std;
  7 
  8 typedef long long ll;
  9 typedef pair<int, int> PII;
 10 const int N = 1010,M=20010;
 11 const int inf=0x3f3f3f3f;
 12 
 13 bool vis[N];
 14 int h[N],e[M],ne[M],w[M];
 15 ll dis[N];
 16 int u[M],v[M],idx,we[M];
 17 int n,m,l,s,t,st;
 18 vector<int> q;
 19 
 20 void add(int a,int b,int c)
 21 {
 22     we[idx]=c;
 23     e[idx]=b;
 24     ne[idx]=h[a];
 25     h[a]=idx++;
 26     
 27 }
 28 
 29 
 30 void dijkstra()
 31 {
 32     priority_queue<PII,vector<PII>,greater<PII>> p;
 33     memset(dis,0x3f,sizeof(dis));
 34     memset(vis,0,sizeof(vis));
 35     
 36     p.push({0,s});
 37     dis[s]=0;
 38     while(p.size())
 39     {
 40         auto t=p.top();
 41         p.pop();
 42         int ver=t.second;
 43         if(vis[ver]) continue;
 44         vis[ver]=true;
 45         for(int i=h[ver];i!=-1;i=ne[i])
 46         {
 47             int j=e[i];
 48             if(dis[j]>dis[ver]+we[i])
 49             {
 50                 dis[j]=dis[ver]+we[i];
 51                 p.push({dis[j],j});
 52             }
 53         }
 54     }
 55     
 56 }
 57 
 58 void printf()
 59 {
 60     puts("Yes");
 61     for(int i=0;i<m;i++)
 62     {
 63         if(w[i])   cout<<u[i]<<" "<<v[i]<<" "<<w[i]<<endl;
 64         else 
 65         {
 66             if(i<st) cout<<u[i]<<" "<<v[i]<<" "<<1<<endl;
 67             else if(i==st) cout<<u[i]<<" "<<v[i]<<" "<<l-dis[t]+1<<endl;
 68             else cout<<u[i]<<" "<<v[i]<<" "<<inf<<endl;
 69         }
 70     }
 71 }
 72 
 73 int main()
 74 {
 75     cin>>n>>m>>l>>s>>t;
 76     memset(h,-1,sizeof(h));
 77     for(int i=0;i<m;i++)
 78     {
 79         cin>>u[i]>>v[i]>>w[i];
 80         if(w[i]==0)
 81         {
 82             q.push_back(i);
 83             continue;
 84         }
 85         add(u[i],v[i],w[i]);
 86         add(v[i],u[i],w[i]);
 87     }
 88     
 89     dijkstra();
 90     if(dis[t]<l) 
 91     {
 92         puts("No");
 93         return 0;
 94     }
 95     else if(dis[t]==l)
 96     {
 97         puts("Yes");
 98         for(int  i=0;i<m;i++)
 99         {
100             if(w[i])
101                 cout<<u[i]<<" "<<v[i]<<" "<<w[i]<<endl;
102             else 
103                 cout<<u[i]<<" "<<v[i]<<" "<<inf<<endl;
104         }
105         return 0;
106     }
107     else
108     {
109         for(int i=0;i<q.size();i++)
110         {
111             add(u[q[i]],v[q[i]],1);
112             add(v[q[i]],u[q[i]],1);
113             dijkstra();
114             if(dis[t]>l)
115             {
116                 continue;
117             }
118             else if(dis[t]<=l)
119             {
120                 st=q[i];
121                 printf();
122                 return 0;
123             }
124         }
125     }
126     puts("No");
127     return 0;
128 }