codeforces 567 E President and Roads (优先队列＋迪杰斯特拉＋tarjan)
题意是说，给定一个有向图，对于每一条边，问是否是s到t的最短路上一定会经过的边．
如果是就输出yes
如果不是，问能否通过减少这条边的权值（减少的权值就是修理费用），使得这条边成为新的最短路上的边．
对于一条边是否一定是最短路上的边，我们可以从s做一遍最短路，然后反响建边，从t再做一遍最短路．
得到两个d1,d2数组
如果一条边d1[u] + d2[v] + w(u, v) = 最短路，那这条边在最短路上的边．但是未必不能缺少．
我们还要判断这条边是否是不能缺少的．
不能缺少的意思是说，如果没有这条边，就不能构成最短路．
那么这条边一定是桥．
我们可以用tarjan算法求桥．
据说是水题，不过图论还没怎么刷，所以对我来说还是很有难度的．
只是基本懂了
下面的代码是我仿照其他人的代码写出来的....求不鄙视 ＞＜
1/*************************************************************************
2 > File Name: code/cf/#314/E.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月17日 星期一 03时09分39秒
6 ************************************************************************/
7#include<iostream>
8#include<iomanip>
9#include<cstdio>
10#include<algorithm>
11#include<cmath>
12#include<cstring>
13#include<string>
14#include<map>
15#include<set>
16#include<queue>
17#include<vector>
18#include<stack>
19#define y0 abc111qqz
20#define y1 hust111qqz
21#define yn hez111qqz
22#define j1 cute111qqz
23#define tm crazy111qqz
24#define lr dying111qqz
25using namespace std;
26#define REP(i, n) for (int i=0;i<int(n);++i)
27typedef long long LL;
28typedef pair<LL,LL> P;
29const int maxn = 200005;
30const LL mod1 = 1e9 + 7;
31const LL mod2 = 99999991;
32const LL inf = 1e15;
33struct Nod{
34 LL b,val,next,idx;
35 void init(LL b,LL val,LL next,LL idx){
36 this->b=b;this->val=val;this->next=next;this->idx=idx;
37 }
38}buf[2][maxn];
39LL len[2],E[2][maxn];
40LL n,m,s,t;
41LL dis[2][maxn],cnt[2][2][maxn],ans1[maxn],ans2[maxn];
42priority_queue<P,vector<P>,greater<P> > q;
43void init()
44{
45 memset(E,-1,sizeof(E));
46 memset(cnt,0,sizeof(cnt));
47 len[0] = len[1] = 0;
48}
49void add_edge(LL a,LL b,LL val,LL idx)
50{
51 buf[0][len[0]].init(b,val,E[0][a],idx);E[0][a]=len[0]++;
52 buf[1][len[1]].init(a,val,E[1][b],idx);E[1][b]=len[1]++;
53}
54void dij(LL s,LL o)
55{
56 while(!q.empty()) q.pop();
57 fill(dis[o],dis[o]+maxn,inf);
58 dis[o][s] = 0;cnt[o][0][s] = cnt[o][1][s] = 1;
59 q.push(P(dis[o][s],s));
60 LL u,v,i;
61 while(!q.empty())
62 {
63 P p = q.top();q.pop();
64 u = p.second;
65 if(dis[o][u] != p.first) continue;
66 for(i=E[o][u];i!=-1;i=buf[o][i].next)
67 {
68 v = buf[o][i].b;
69 if(dis[o][v] > dis[o][u] + buf[o][i].val)
70 {
71 dis[o][v] = dis[o][u] + buf[o][i].val;
72 cnt[o][0][v] = cnt[o][0][u];
73 cnt[o][1][v] = cnt[o][1][u];
74 q.push(P(dis[o][v],v));
75 }else if(dis[o][v] == dis[o][u] + buf[o][i].val){
76 cnt[o][0][v] = (cnt[o][0][v] + cnt[o][0][u]) % mod1;
77 cnt[o][1][v] = (cnt[o][1][v] + cnt[o][1][u]) % mod2;
78 }
79 }
80 }
81}
82int main()
83{
84 init();
85 LL u,v,i,a,b,val;
86 LL cost;
87 cin>>n>>m>>s>>t;
88 for(i=1;i<=m;i++){
89 cin>>a>>b>>val;
90 add_edge(a,b,val,i);
91 }
92 dij(s,0);dij(t,1);
93 for(u=1;u<=n;u++)
94 {
95 for(i=E[0][u];i!=-1;i=buf[0][i].next){
96 v = buf[0][i].b;
97 if(dis[0][u]+dis[1][v]+buf[0][i].val==dis[0][t]){
98 if(cnt[0][0][u]*cnt[1][0][v]%mod1 == cnt[0][0][t]&&
99 cnt[0][1][u]*cnt[1][1][v]%mod2 == cnt[0][1][t]){
100 ans1[buf[0][i].idx] = 1;
101 continue;
102 }
103 }
104 cost = dis[0][u]+dis[1][v]+buf[0][i].val-dis[0][t]+1;
105 if(buf[0][i].val - cost > 0){
106 ans1[buf[0][i].idx] = 0;
107 ans2[buf[0][i].idx] = cost;
108 }else{
109 ans1[buf[0][i].idx] = -1;
110 }
111 }
112 }
113 for(i=1;i<=m;i++){
114 if(ans1[i] == 1) printf("YES\n");
115 else if(ans1[i] == -1) printf("NO\n");
116 else{
117 printf("CAN %I64d\n",ans2[i]);
118 }
119 }
120 return 0;
121}