题意：给定n个点,m条边，以及起点s，终点t，问你图中是否存在s->t的最短路为L，其中权值为0的可以任意修改。
思路：对给定的边分为2类，权重不为0的直接扔进去建图，权重为0的边先存起来。接着跑一遍堆优化的dij，如果dis[t]小于L，那么无论怎么修改权重0的边都没有办法凑出最短路L；
如果dis[t]=L,那么直接输出；如果dis[t]>L,则将原来事先存起来的边一条一条的加进去，权值设为1。每加一条边就跑一次dij，一旦找到dis[t]<=L，就可以终止并输出。
PS：原来堆优化的dij就是用优先队列优化，自己敲了一遍才知道，看来模板这东西得多敲才会懂。。。
1 #include <iostream> 2 #include <queue> 3 #include <stack> 4 #include <cstdio> 5 #include <vector> 6 #include <map> 7 #include <set> 8 #include <bitset> 9 #include <algorithm> 10 #include <cmath> 11 #include <cstring> 12 #include <cstdlib> 13 #include <string> 14 #include <sstream> 15 #include <time.h> 16 #define x first 17 #define y second 18 #define pb push_back 19 #define mp make_pair 20 #define lson l,m,rt*2 21 #define rson m+1,r,rt*2+1 22 #define mt(A,B) memset(A,B,sizeof(A)) 23 #define mod 1000000007 24 using namespace std; 25 typedef long long LL; 26 const double PI = acos(-1); 27 const int N=30000+10; 28 const int inf = 0x3f3f3f3f; 29 //const LL INF=0x3f3f3f3f3f3f3f3fLL; 30 const LL INF=1e15; 31 struct node 32 { 33 int u,v,next; 34 LL w; 35 } E[N]; 36 int n,m,s,t,top=0,head[N]; 37 LL L,dis[N]; 38 bool vis[N]; 39 vector<node> P; 40 void add(int u,int v,LL w) 41 { 42 E[top].u=u; 43 E[top].v=v; 44 E[top].w=w; 45 E[top].next=head[u]; 46 head[u]=top++; 47 } 48 struct Node//堆优化的dij所用的结构体 49 { 50 int v;//点 51 LL d;//距离 52 Node(int v=0,LL d=0):v(v),d(d) {}//我也不懂为什么这样写，反正照写就对了 53 bool operator <(const Node &r)const 54 { 55 return d>r.d; 56 } 57 }; 58 void dij() 59 { 60 for(int i=0; i<N; i++)//先初始化 61 { 62 dis[i]=INF; 63 vis[i]=false; 64 } 65 dis[s]=0; 66 priority_queue<Node> Q; 67 Q.push(Node(s,0)); 68 while(!Q.empty()) 69 { 70 Node p=Q.top(); 71 Q.pop(); 72 if(vis[p.v])continue; 73 vis[p.v]=true; 74 for(int i=head[p.v]; i!=-1; i=E[i].next) 75 { 76 int v=E[i].v; 77 if(!vis[v]&&dis[v]>dis[p.v]+E[i].w)//松弛法 78 { 79 dis[v]=dis[p.v]+E[i].w; 80 Q.push(Node(v,dis[v])); 81 } 82 } 83 } 84 } 85 int main() 86 { 87 #ifdef Local 88 freopen("data.txt","r",stdin); 89 #endif 90 int u,v; 91 LL w; 92 mt(head,-1);//邻接表初始化 93 cin>>n>>m>>L>>s>>t; 94 for(int i=0; i<m; i++)//先将节点分类，w!=0的先加进去建图 95 { 96 cin>>u>>v>>w; 97 if(w) 98 { 99 add(u,v,w); 100 add(v,u,w); 101 } 102 else 103 { 104 node p; 105 p.u=u; 106 p.v=v; 107 p.w=w; 108 p.next=-1; 109 P.pb(p); 110 } 111 } 112 dij(); 113 if(dis[t]<L) 114 { 115 puts("NO"); 116 } 117 else if(dis[t]==L) 118 { 119 puts("YES"); 120 for(int i=0; i<top; i+=2) 121 { 122 printf("%d %d %I64d\n",E[i].u,E[i].v,E[i].w); 123 } 124 for(int i=0; i<P.size(); i++) 125 { 126 printf("%d %d %I64d\n",P[i].u,P[i].v,INF); 127 } 128 } 129 else 130 { 131 int pos=0,flag=0; 132 for(pos=0; pos<P.size(); pos++) 133 { 134 add(P[pos].u,P[pos].v,1); 135 add(P[pos].v,P[pos].u,1); 136 dij(); 137 if(dis[t]<=L) 138 { 139 E[top-1].w+=L-dis[t]; 140 E[top-2].w+=L-dis[t]; 141 flag=1; 142 break; 143 } 144 } 145 if(!flag)puts("NO"); 146 else 147 { 148 puts("YES"); 149 for(int i=0; i<top; i+=2) 150 { 151 printf("%d %d %I64d\n",E[i].u,E[i].v,E[i].w); 152 } 153 for(int i=pos+1; i<P.size(); i++) 154 { 155 printf("%d %d %I64d\n",P[i].u,P[i].v,INF); 156 } 157 } 158 } 159 #ifdef Local 160 cerr << "time: " << (LL) clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl; 161 #endif 162 }