Codeforces 567E President and Roads 题解

题意

给定一张有向图，起点和终点，问对于每一条边，走从起点到终点的一条最短路，是否一定经过它，如果不是，有没有可能通过减小它的权值使得一定经过它，有可能的话最少需要减多少，权值需要都为正整数

思路

由起点到终点跑一遍最短路，再将边反向从终点到起点跑一遍，这样可以判断出对于每一条边，它现在在不在从起点到终点的最短路上，对于在的边，我们建一张新的无向图把它加进去，通过求强连通分量的过程，我们可以判断出它是否是必经的，如果不是的话，我们看一下当前最短路的值和经过这条路的最短路的值，把这条路的权值减小到使得后者小于前者即可

代码

#include <cstdio> #include <vector> #include <algorithm> #include <queue> #define INF 1000000000000000000LL using namespace std; long long a[100001],b[100001],l[100001]; long long d1[100001],d2[100001]; bool bridge[100001]; vector<pair<long long,long long> > edge[100001]; long long index; long long dfn[100001],low[100001]; long long n,m,s,t; bool vis[100001]; void dijkstra(long long v,long long *d) { long long t; priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > > pq; for(long long i=1;i<=n;i++) d[i]=INF; d[v]=0; pq.push(make_pair(0,v)); while(!pq.empty()) { t=pq.top().second; pq.pop(); for(long long i=0;i<edge[t].size();i++) if(d[edge[t][i].first]>d[t]+edge[t][i].second) { d[edge[t][i].first]=d[t]+edge[t][i].second; pq.push(make_pair(d[edge[t][i].first],edge[t][i].first)); } } return; } void tarjan(long long x) { index++; dfn[x]=index; low[x]=index; for(long long i=0;i<edge[x].size();i++) { if(vis[edge[x][i].second]) continue; vis[edge[x][i].second]=true; if(!dfn[edge[x][i].first]) { tarjan(edge[x][i].first); low[x]=min(low[x],low[edge[x][i].first]); if(dfn[x]<low[edge[x][i].first]) bridge[edge[x][i].second]=true; } else low[x]=min(low[x],dfn[edge[x][i].first]); } //printf("x:%I64d dfn:%I64d low:%I64d\n",x,dfn[x],low[x]); return; } int main() { scanf("%I64d%I64d%I64d%I64d",&n,&m,&s,&t); for(long long i=0;i<m;i++) scanf("%I64d%I64d%I64d",&a[i],&b[i],&l[i]); for(long long i=0;i<m;i++) edge[a[i]].push_back(make_pair(b[i],l[i])); dijkstra(s,d1); for(long long i=1;i<=n;i++) edge[i].clear(); for(long long i=0;i<m;i++) edge[b[i]].push_back(make_pair(a[i],l[i])); dijkstra(t,d2); for(long long i=1;i<=n;i++) edge[i].clear(); for(long long i=0;i<m;i++) if(d1[a[i]]+l[i]+d2[b[i]]==d1[t]) { edge[a[i]].push_back(make_pair(b[i],i)); edge[b[i]].push_back(make_pair(a[i],i)); //printf("a:%I64d b:%I64d\n",a[i],b[i]); } tarjan(s); for(long long i=0;i<m;i++) { if(bridge[i]) printf("YES\n"); else if(d1[t]-d1[a[i]]-d2[b[i]]-1>0) printf("CAN %I64d\n",l[i]-(d1[t]-d1[a[i]]-d2[b[i]]-1)); else printf("NO\n"); } return 0; }