codeforces 567 E President and Roads (优先队列+迪杰斯特拉+tarjan)

题意是说,给定一个有向图,对于每一条边,问是否是s到t的最短路上一定会经过的边.

如果是就输出yes

如果不是,问能否通过减少这条边的权值(减少的权值就是修理费用),使得这条边成为新的最短路上的边.

对于一条边是否一定是最短路上的边,我们可以从s做一遍最短路,然后反响建边,从t再做一遍最短路.

得到两个d1,d2数组

如果一条边d1[u] + d2[v] + w(u, v) = 最短路,那这条边在最短路上的边.但是未必不能缺少.

我们还要判断这条边是否是不能缺少的.

不能缺少的意思是说,如果没有这条边,就不能构成最短路.

那么这条边一定是桥.

我们可以用tarjan算法求桥.

据说是水题,不过图论还没怎么刷,所以对我来说还是很有难度的.

只是基本懂了

下面的代码是我仿照其他人的代码写出来的....求不鄙视 ><

  1/*************************************************************************
  2	> File Name: code/cf/#314/E.cpp
  3	> Author: 111qqz
  4	> Email: rkz2013@126.com 
  5	> Created Time: 2015年08月17日 星期一 03时09分39秒
  6 ************************************************************************/
  7#include<iostream>
  8#include<iomanip>
  9#include<cstdio>
 10#include<algorithm>
 11#include<cmath>
 12#include<cstring>
 13#include<string>
 14#include<map>
 15#include<set>
 16#include<queue>
 17#include<vector>
 18#include<stack>
 19#define y0 abc111qqz
 20#define y1 hust111qqz
 21#define yn hez111qqz
 22#define j1 cute111qqz
 23#define tm crazy111qqz
 24#define lr dying111qqz
 25using namespace std;
 26#define REP(i, n) for (int i=0;i<int(n);++i)  
 27typedef long long LL;
 28typedef pair<LL,LL> P;
 29const int maxn = 200005;
 30const LL mod1 = 1e9 + 7;
 31const LL mod2 = 99999991;
 32const LL inf = 1e15;
 33struct Nod{
 34    LL b,val,next,idx;
 35    void init(LL b,LL val,LL next,LL idx){
 36        this->b=b;this->val=val;this->next=next;this->idx=idx;
 37    }
 38}buf[2][maxn];
 39LL len[2],E[2][maxn];
 40LL n,m,s,t;
 41LL dis[2][maxn],cnt[2][2][maxn],ans1[maxn],ans2[maxn];
 42priority_queue<P,vector<P>,greater<P> > q;
 43void init()
 44{
 45    memset(E,-1,sizeof(E));
 46    memset(cnt,0,sizeof(cnt));
 47    len[0] = len[1] = 0;
 48}
 49void add_edge(LL a,LL b,LL val,LL idx)
 50{
 51    buf[0][len[0]].init(b,val,E[0][a],idx);E[0][a]=len[0]++;
 52    buf[1][len[1]].init(a,val,E[1][b],idx);E[1][b]=len[1]++;
 53}
 54void dij(LL s,LL o)
 55{
 56    while(!q.empty()) q.pop();
 57    fill(dis[o],dis[o]+maxn,inf);
 58    dis[o][s] = 0;cnt[o][0][s] = cnt[o][1][s] = 1;
 59    q.push(P(dis[o][s],s));
 60    LL u,v,i;
 61    while(!q.empty())
 62    {
 63        P p = q.top();q.pop();
 64        u = p.second;
 65        if(dis[o][u] != p.first) continue;
 66        for(i=E[o][u];i!=-1;i=buf[o][i].next)
 67	{
 68            v = buf[o][i].b;
 69            if(dis[o][v] > dis[o][u] + buf[o][i].val)
 70	    {
 71                 dis[o][v] = dis[o][u] + buf[o][i].val;
 72                cnt[o][0][v] = cnt[o][0][u];
 73                cnt[o][1][v] = cnt[o][1][u];
 74                q.push(P(dis[o][v],v));
 75            }else if(dis[o][v] == dis[o][u] + buf[o][i].val){
 76                 cnt[o][0][v] = (cnt[o][0][v] + cnt[o][0][u]) % mod1;
 77                cnt[o][1][v] = (cnt[o][1][v] + cnt[o][1][u]) % mod2;
 78            }
 79        }
 80    }
 81}
 82int main()
 83{
 84    init();
 85    LL u,v,i,a,b,val;
 86    LL cost;
 87    cin>>n>>m>>s>>t;
 88    for(i=1;i<=m;i++){
 89        cin>>a>>b>>val;
 90        add_edge(a,b,val,i);
 91    }
 92    dij(s,0);dij(t,1);
 93    for(u=1;u<=n;u++)
 94    {
 95        for(i=E[0][u];i!=-1;i=buf[0][i].next){
 96            v = buf[0][i].b;
 97            if(dis[0][u]+dis[1][v]+buf[0][i].val==dis[0][t]){
 98                 if(cnt[0][0][u]*cnt[1][0][v]%mod1 == cnt[0][0][t]&&
 99                   cnt[0][1][u]*cnt[1][1][v]%mod2 == cnt[0][1][t]){
100                     ans1[buf[0][i].idx] = 1;
101                    continue;
102                }
103            }
104            cost = dis[0][u]+dis[1][v]+buf[0][i].val-dis[0][t]+1;
105            if(buf[0][i].val - cost > 0){
106                ans1[buf[0][i].idx] = 0;
107                ans2[buf[0][i].idx] = cost; 
108            }else{
109                ans1[buf[0][i].idx] = -1;
110            }
111        }
112    }
113    for(i=1;i<=m;i++){
114        if(ans1[i] == 1) printf("YES\n");
115        else if(ans1[i] == -1) printf("NO\n");
116        else{
117	    printf("CAN %I64d\n",ans2[i]);
118        }
119    }
120    return 0;
121}