题目链接：
http://codeforces.com/contest/567/problem/E
题意：
给你一个带重边的图，求三类边：
在最短路构成的DAG图中，哪些边是必须经过的；
其他的（包括不在DAG上的边）不是必须经过的边把权值改小多少才能通过，
或者根本不可能通过的。
题解：
从起点s跑一遍最短路得到d[maxn]，从终点t跑一遍最短路得到d2[maxn]，对于边（u,v,w），如果d[u]+d2[v]+w==d[t]那么这条边在最短路上，对于不在最短路上的边，如果d[u]+d2[v]+w-d[t]+1<w则可以重建，否则输出NO。
对于所有最短路构成的DAG（建成无向图）跑一遍tarjan求割边，所有的割边输出YES。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std; typedef __int64 LL;
#define INF (1LL<<61) struct Edge {
int u, v, type,bri,id;
LL w;
Edge(int u, int v, LL w,int id) :u(u), v(v), w(w), type(),bri(),id(id) {}
}; void addEdge(vector<int> G[],vector<Edge> &egs,int u, int v, int w,int id=) {
egs.push_back(Edge(u, v, w,id));
G[u].push_back(egs.size() - );
} const int maxn = 2e5 + ;
const int maxm = maxn * ;
int n, m, s, t; vector<int> G[maxn],G2[maxn];
vector<Edge> egs,egs2; struct Heap {
int v; LL d;
Heap(int v, LL d) :v(v), d(d) {}
bool operator < (Heap tmp) const {
return d > tmp.d;
}
}; LL d[maxn], d2[maxn];
int done[maxn];
void dijkstral(vector<int> G[], vector<Edge> &egs,LL *d, int s) {
for (int i = ; i < maxn; i++) d[i] = INF;
memset(done, , sizeof(done));
priority_queue<Heap> pq;
d[s] = , pq.push(Heap(s,));
while (!pq.empty()) {
int u = pq.top().v; pq.pop();
if (done[u]) continue;
done[u] = ;
for (int i = ; i < G[u].size(); i++) {
Edge& e = egs[G[u][i]];
if (d[e.v] > d[u] + e.w) {
d[e.v] = d[u] + e.w;
pq.push(Heap(e.v, d[e.v]));
}
}
}
} vector<int> DAG[maxn];
vector<Edge> egs3; int pre[maxn], low[maxn], dfs_clock;
int dfs(vector<int> G[],vector<Edge> &egs,int u) {
int lowu = pre[u] = ++dfs_clock;
int child = ;
for (int i = ; i < G[u].size(); i++) {
Edge &e = egs[G[u][i]];
if (e.type == ) continue;
egs[G[u][i] ^ ].type = ;
if (!pre[e.v]) {
child++;
int lowv = dfs(G, egs, e.v);
lowu = min(lowu, lowv);
if (lowv > pre[u]) {
e.bri = ;
}
}
else if (pre[e.v] < pre[u]) {
lowu = min(lowu, pre[e.v]);
}
}
low[u] = lowu;
return lowu;
} int main() {
scanf("%d%d%d%d", &n, &m, &s, &t),s--,t--;
for (int i = ; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w),u--,v--;
addEdge(G,egs,u, v, w);
addEdge(G2, egs2, v, u, w);
}
dijkstral(G,egs,d,s);
dijkstral(G2, egs2,d2, t); for (int i = ; i < egs.size(); i++) {
Edge& e = egs[i];
if (e.w+d[e.u]+d2[e.v]==d[t]) {
addEdge(DAG, egs3, e.u, e.v, e.w,i);
addEdge(DAG, egs3, e.v, e.u, e.w,i);
}
} memset(pre, , sizeof(pre));
dfs_clock = ;
dfs(DAG, egs3, s);
for (int i = ; i < egs3.size(); i++) {
Edge& e = egs3[i];
if (e.bri) {
egs[e.id].bri = ;
}
}
for (int i = ; i < egs.size(); i++) {
Edge& e = egs[i];
if (e.bri) printf("YES\n");
else {
LL delta = d[e.u] + d2[e.v] + e.w - d[t] + ;
if (delta<e.w) printf("CAN %I64d\n", delta);
else printf("NO\n");
}
}
return ;
}
总结：
这题跳了两个坑：
1、距离和会爆int：
发现问题之后改了d[maxn]，但是一直没发现Heap结构体里面的d没有改！！！！wa了七八次！
2、卡spfa的时间！！！
。。
代码调试出错误的时候，改正一定要彻底！不要有的地方改了有的地方漏了！比如dijkstra，改了d还要改Heap结构体！！！