567E - President and Roads - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define dbg(x) cout << (#x) << " = " << x << endl
#define dbg2(x, y) cout << (#x) << " = " << x << ", " << #y << " = " << y << endl
const ll maxn = 2e5 + 69;
const ll inf = 1e18;
ll n,m,s,f;
ll u,v,cost;
struct query{
	ll u,v;
	ll cost;
};
vector<pair<ll,ll>> adj_s[maxn],adj_t[maxn];
ll pre_s[maxn],used_s[maxn],dist_s[maxn];
ll pre_t[maxn],used_t[maxn],dist_t[maxn];
vector<query> Q;
vector<ll> ans;
vector<query> shortest_path;
map<ll,pair<ll,ll> > mp;
bool cmp(query a,query b){
	if(dist_s[a.u] == dist_s[b.u]){
		return dist_s[a.v] < dist_s[b.v];
	}
	return dist_s[a.u] < dist_s[b.u];
}
void dijkstra(ll s){
	priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
	pq.push({0,s});
	for(int i = 1;i<=n;i++){
		dist_s[i] = inf;
	}
	dist_s[s] = 0;
	pre_s[s] = -1;
	while(!pq.empty()){
		ll u = pq.top().second;
		//cout << u << endl;
		if(u == f) break;
		pq.pop();
		if(used_s[u]) continue;
		used_s[u] = 1;
		for(auto v:adj_s[u]){
			ll next = v.first,w = v.second;
			ll temp = dist_s[u] + w;
			if(temp < dist_s[next]){
				//pre[next] = u;
				dist_s[next] = temp;
				pq.push({temp,v.first});
			}
		}
	}
}
void dijkstra_2(ll t){
	priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
	pq.push({0,t});
	for(int i = 1;i<=n;i++){
		dist_t[i] = inf;
	}
	dist_t[t] = 0;
	pre_t[t] = -1;
	while(!pq.empty()){
		ll u = pq.top().second;
		//cout << u << endl;
		if(u == s) break;
		pq.pop();
		if(used_t[u]) continue;
		used_t[u] = 1;
		for(auto v:adj_t[u]){
			ll next = v.first,w = v.second;
			ll temp = dist_t[u] + w;
			if(temp < dist_t[next]){
				//pre[next] = u;
				dist_t[next] = temp;
				pq.push({temp,v.first});
			}
		}
	}
}
int main(){
	cin >> n >> m >> s >> f;
	for(int i = 1;i<=m;i++){
		cin >> u >> v >> cost;
		adj_s[u].push_back({v,cost});
		adj_t[v].push_back({u,cost});
		Q.push_back({u,v,cost});
	}
	dijkstra(s);
	dijkstra_2(f);
	/*for(int i = 1;i<=n;i++){
		cout << dist_s[i] << " ";
	}
	cout << endl;
	for(int i = 1;i<=n;i++){
		cout << dist_t[i] << " ";
	}
	cout << endl;*/
	for(int i = 0;i<m;i++){
		//cout << Q[i].u << " " << Q[i].v << endl;
		//cout << dist_s[Q[i].u] << " " <<  Q[i].cost << " " <<  dist_t[Q[i].v] << endl;
		if(dist_s[Q[i].u] == inf || dist_t[Q[i].v] == inf) continue;
		if(dist_s[Q[i].u] + Q[i].cost + dist_t[Q[i].v] == dist_s[f]){
			shortest_path.push_back(Q[i]);
		}
	}
	sort(shortest_path.begin(),shortest_path.end(),cmp);
	ll check = 1;
	query prev = shortest_path[0];
	for(int i = 1;i<(ll)shortest_path.size();i++){
		//dbg2(shortest_path[i].u,shortest_path[i].v);
		//dbg(prev.v);
		if(dist_s[shortest_path[i].u] < dist_s[prev.v]){
			check = 0;
		}else{
			if(check){
				mp.insert({prev.u,{prev.v,prev.cost}});
				//cout << "se" << endl;
			}
			check = 1;
		}
		if(dist_s[shortest_path[i].v] >= dist_s[prev.v]){
			prev = shortest_path[i];
		}
	}
	/*cout << check << endl;
	cout << "check" << endl;
	dbg(prev.u);*/
	if(check) mp.insert({prev.u,{prev.v,prev.cost}});
	for(int i = 0;i<m;i++){
		if(mp.find(Q[i].u) != mp.end() && mp[Q[i].u].first == Q[i].v && mp[Q[i].u].second == Q[i].cost){
			cout << "YES" << endl;
		}else{
			if(dist_s[Q[i].u] == inf || dist_t[Q[i].v] == inf || dist_s[f] - dist_s[Q[i].u] - dist_t[Q[i].v] - 1 <= 0){
				cout << "NO" << endl;
			}else cout << "CAN " << dist_s[Q[i].u] + Q[i].cost + dist_t[Q[i].v] - (dist_s[f] - 1) << endl;
		}
	}
}