E. President and Roads
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/567/problem/E
Description
Berland has n cities, the capital is located in city s, and the historic home town of the President is in city t (s ≠ t). The cities are connected by one-way roads, the travel time for each of the road is a positive integer.
Once a year the President visited his historic home town t, for which his motorcade passes along some path from s to t (he always returns on a personal plane). Since the president is a very busy man, he always chooses the path from s to t, along which he will travel the fastest.
The ministry of Roads and Railways wants to learn for each of the road: whether the President will definitely pass through it during his travels, and if not, whether it is possible to repair it so that it would definitely be included in the shortest path from the capital to the historic home town of the President. Obviously, the road can not be repaired so that the travel time on it was less than one. The ministry of Berland, like any other, is interested in maintaining the budget, so it wants to know the minimum cost of repairing the road. Also, it is very fond of accuracy, so it repairs the roads so that the travel time on them is always a positive integer.
Input
The first lines contain four integers n, m, s and t (2 ≤ n ≤ 105; 1 ≤ m ≤ 105; 1 ≤ s, t ≤ n) — the number of cities and roads in Berland, the numbers of the capital and of the Presidents' home town (s ≠ t).
Next m lines contain the roads. Each road is given as a group of three integers ai, bi, li (1 ≤ ai, bi ≤ n; ai ≠ bi; 1 ≤ li ≤ 106) — the cities that are connected by the i-th road and the time needed to ride along it. The road is directed from city ai to city bi.
The cities are numbered from 1 to n. Each pair of cities can have multiple roads between them. It is guaranteed that there is a path froms to t along the roads.
Output
Print m lines. The i-th line should contain information about the i-th road (the roads are numbered in the order of appearance in the input).
If the president will definitely ride along it during his travels, the line must contain a single word "YES" (without the quotes).
Otherwise, if the i-th road can be repaired so that the travel time on it remains positive and then president will definitely ride along it, print space-separated word "CAN" (without the quotes), and the minimum cost of repairing.
If we can't make the road be such that president will definitely ride along it, print "NO" (without the quotes).
Sample Input
6 7 1 6
1 2 2
1 3 10
2 3 7
2 4 8
3 5 3
4 5 2
5 6 1
Sample Output
YES
CAN 2
CAN 1
CAN 1
CAN 1
CAN 1
YES
HINT
题意
一个有向带重边的图，对于每条边，问你最短路是否必须进过这条边，否则的话，问你最少减少这条边的边权多少，就可以最短路经过这个边了
如果还是不行的话，就输出NO
题解：
比较裸的题，跑一发正常的最短路，然后建反向边，跑一发最短路，YES的判断是由带重边的tarjan来求，求桥边就好了
代码来自zenzentorwie
代码
#include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include <queue> using namespace std; const int maxn = 200010; #define INF (1LL<<61) typedef long long ll; struct Dijkstra { struct node { ll d; int u; bool operator < (const node& b) const { return d > b.d; } node() {} node(ll _d, int _u): d(_d), u(_u) {} }; struct Edge { int from, to, id; ll dist; Edge() {} Edge(int u, int v, ll w) : from(u), to(v), dist(w){} }; int n, m; vector<Edge> edges; vector<int> G[maxn]; bool done[maxn]; ll d[maxn]; int p[maxn]; void init(int n) { this->n = n; for (int i = 0; i <= n; i++) G[i].clear(); edges.clear(); } void addEdge(int from, int to, ll dist) { edges.push_back(Edge(from, to, dist)); m = edges.size(); G[from].push_back(m-1); } void dijkstra(int s) { priority_queue<node> Q; for (int i = 0; i <= n; i++) d[i] = INF; d[s] = 0; memset(done, 0, sizeof(done)); Q.push(node(0, s)); while (!Q.empty()) { node x = Q.top(); Q.pop(); int u = x.u; if (done[u]) continue; done[u] = true; for (int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if (d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; Q.push(node(d[e.to], e.to)); } } } } } S, T; int dfn[maxn]; // 时间戳 int dfs_clock; // dfs时间变量 int low[maxn]; // u及u的后代在DFS树上能够到达的最早的祖先 struct Edge { int u, v, w, id; Edge(int a=0, int b=0, int w=0, int c=0) : u(a), v(b), w(w), id(c) {} } e[2*maxn]; vector<Edge> G[maxn]; bool isbridge[2*maxn]; int dfs(int u, int la) { int lowu = dfn[u] = ++dfs_clock; // dfs_clock在调用dfs前要初始化为0 int child = 0; // 子节点个数 for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].v; if (!dfn[v]) { // 未访问过，树边 int lowv = dfs(v, G[u][i].id); lowu = min(lowu, lowv); if (lowv > dfn[u]) { // 判断桥 isbridge[G[u][i].id] = 1; } } else if (dfn[v] < dfn[u] && G[u][i].id != la) { // 反向边 lowu = min(lowu, dfn[v]); } } low[u] = lowu; return lowu; } int ison[2*maxn]; int can[2*maxn]; int main() { int n, m, s, t; scanf("%d%d%d%d", &n, &m, &s, &t); S.init(n+1); T.init(n+1); int u, v, w; for (int i = 1; i <= m; i++){ scanf("%d%d%d", &u, &v, &w); e[i] = Edge(u, v, w, i); S.addEdge(u, v, w); T.addEdge(v, u, w); } S.dijkstra(s); T.dijkstra(t); ll ddd = S.d[t]; ll delta; if (S.d[t] == INF) { for (int i = 1; i <= m; i++) printf("NO "); } else { for (int i = 1; i <= m; i++) { u = e[i].u; v = e[i].v; w = e[i].w; if (S.d[u] + w == S.d[v] && T.d[v] + w == T.d[u]) { G[u].push_back(Edge(u, v, w, i)); G[v].push_back(Edge(v, u, w, i)); ison[i] = 1; } } dfs(s, -1); for (int i = 1; i <= m; i++) { if (isbridge[i]) { printf("YES "); } else { delta = S.d[e[i].u] + T.d[e[i].v] + e[i].w - ddd + 1; if (delta < e[i].w) printf("CAN %I64d ", delta); else printf("NO "); } } } return 0; }