题目描述
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.
输入格式
The first lines contain four integers $ n $ , $ m $ , $ s $ and $ t $ ( $ 2<=n<=10^{5}; 1<=m<=10^{5}; 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 $ a_{i},b_{i},l_{i} $ ( $ 1<=a_{i},b_{i}<=n; a_{i}≠b_{i}; 1<=l_{i}<=10^{6} $ ) — the cities that are connected by the $ i $ -th road and the time needed to ride along it. The road is directed from city $ a_{i} $ to city $ b_{i} $ .
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 from $ s $ to $ t $ along the roads.
输出格式
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).
提示
The cost of repairing the road is the difference between the time needed to ride along it before and after the repairing.
题意简述
总统要回家，即从 \(s\) 走到 \(t\)，会经过一些街道，每条街道都是单向的并且拥有权值。现在，为了让总统更好的回家，要对每一条街道进行操作：
-
如果该街道一定在最短路上，则输出“YES” 。
-
如果该街道修理过后，该边所在的最短路可以取代原先的最短路，则输出“CAN \(x\)” ， \(x\) 是修改该街道的最小花费，就是权值减小的值。
-
如果该街道不在 \(s\) 到 \(t\) 的路径上，或者修改过后权值小于等于０，则输出“NO”。
最短路好题,*2200 刚刚好,就是写起来有点折磨人。
如何确定一条边是否必经？
正反图两遍统计一下最短路的数量。
设 \(s \rightarrow x\) 的方案有 \(c_1\) 种，\(y \rightarrow t\) 的方案有 \(c_2\) 种，设 \(s \rightarrow t\) 的方案有 \(c\) 种，
如果一条边必经，那么必然满足 \(c_1 \times c_2 = c\)。
然而方案数可能很大，于是需要 hash。
为了保证答案是对的，还要验证一下 \(dis_{s,x} + l_{x,y} + dis_{y,t}\) 是否等于 \(dis_{s,t}\) 。
一般来说最好写双哈，但这题放了单 hash，于是偷了懒daze。
CAN 和 NO 与 YES 类似，看看要减多少才能成为最短路的长度，然后再减一使最短路强制经过。
如果边权减没了，输出 NO 就好了
代码实现
正图反图真麻烦啊。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define mod 998244353ll
using namespace std;
using ll=long long;
const int N=1e5+5,M=1e5+5;
const ll inf=1e16+5;
int n,m,s,t;
struct graph{
struct edge{int to,next,val;}e[M<<1];
int head[N],idx=1;
void init(){memset(head,0,sizeof(head));}
inline void add(int from,int to,int val){
e[++idx].to=to;
e[idx].val=val;
e[idx].next=head[from];
head[from]=idx;
}
}S[2];
struct edge{int from,to,val;}e[M<<1];
struct node{
int pos;ll val;
friend bool operator<(node x,node y){
return x.val>y.val;
}
};
priority_queue<node>q;
ll dis[N][2],cnt[N][2];
bool vis[N];
void dijkstra(int st,int op){
for(int i=1;i<=n;i++){
dis[i][op]=inf,cnt[i][op]=0;
vis[i]=0;
}
q.push((node){st,0});
dis[st][op]=0,cnt[st][op]=1;
while(q.size()){
int p=q.top().pos;
q.pop();
if(vis[p])continue;
vis[p]=1;
for(int i=S[op].head[p];i;i=S[op].e[i].next){
int to=S[op].e[i].to;
if(dis[to][op]>dis[p][op]+S[op].e[i].val){
dis[to][op]=dis[p][op]+S[op].e[i].val;
cnt[to][op]=cnt[p][op];
q.push((node){to,dis[to][op]});
}
else if(dis[to][op]==dis[p][op]+S[op].e[i].val){
(cnt[to][op]+=cnt[p][op])%=mod;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>s>>t;
S[0].init(),S[1].init();
for(int i=1,x,y,v;i<=m;i++){
cin>>x>>y>>v;
e[i]=(edge){x,y,v};
S[0].add(x,y,v),S[1].add(y,x,v);
}
dijkstra(s,0);dijkstra(t,1);
for(int i=1;i<=m;i++){
int x=e[i].from,y=e[i].to,v=e[i].val;
if(dis[x][0]+v+dis[y][1]==dis[t][0]&&cnt[x][0]*cnt[y][1]%mod==cnt[t][0]){
cout<<"YES"<<'\n';
}
else {
ll k=dis[t][0]-dis[x][0]-dis[y][1];
if(k<=1)cout<<"NO"<<'\n';
else cout<<"CAN "<<v-k+1<<'\n';
}
}
return 0;
}
//iictiw-marisa