codeforces 567 E. President and Roads 【 最短路 桥 】

给出一个有向图，从起点走到终点（必须走最短路），问一条边是否一定会被经过，如果不经过它，可以减小它的多少边权使得经过它（边权不能减少到0）

正反向建图，分别求出起点到每个点的最短距离，终点到每个点的最短距离（用这个可以算出减小的边权）

再将在最短路径上的边重新建图。求出里面的桥，就是必须经过的边

wa了一上午------呜呜呜呜

先wa 19  是因为求桥的时候是无向图，数组开小了一半

然后 wa 46 ，是因为dis[]数组初始化为 1 << 30 -1 ,应该再开大点 ，开成 1 << 50 -1

我写成 1 LL * 50 -----一直wa 19------

5555555555555555555--------sad-------

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
#define lp (p << 1)
#define rp (p << 1|1)
#define getmid(l,r) (l + (r - l) / 2)
#define MP(a,b) make_pair(a,b)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int INF = (1 << 30) - 1;
const int maxn = 100055;

int N,M;
ll path;
int first1[maxn],nxt1[10 * maxn],ecnt1;
int first2[maxn],nxt2[10 *maxn],ecnt2;
int first[maxn],nxt[10*maxn],ecnt;
ll dis1[maxn],dis2[maxn];

int bg[20*maxn],vis[20*maxn],low[maxn],dfn[maxn];
int ans[20*maxn],res[maxn];
int tot,num;

struct edge{
    int v,u,cost;
    int tag;
    int ge;
    int id;
    friend bool operator < (edge a,edge b){
        return a.cost > b.cost;
    }
};

edge e1[5*maxn],e2[5*maxn],e[5*maxn];

void init(){
    ecnt1 = ecnt2 = ecnt = 0;
    memset(first1,-1,sizeof(first1));
    memset(first2,-1,sizeof(first2));
    memset(first,-1,sizeof(first));
}

void Add_edge1(int u,int v,int c){
    nxt1[++ecnt1] = first1[u];
    e1[ecnt1].u = u;
    e1[ecnt1].v = v;
    e1[ecnt1].cost = c;
    e1[ecnt1].tag = 0;
    e1[ecnt1].ge = 0;
    first1[u] = ecnt1;
}

void Add_edge2(int u,int v,int c){
    nxt2[++ecnt2] = first2[u];
    e2[ecnt2].v = v;
    e2[ecnt2].cost = c;
    e2[ecnt2].tag = 0;
    e2[ecnt2].ge = 0;
    first2[u] = ecnt2;
}

void Add_edge(int u,int v,int c){
    nxt[ecnt] = first[u];
    e[ecnt].v = v;
    e[ecnt].u = u;
    e[ecnt].id = c;
    first[u] = ecnt++;
    
    nxt[ecnt] = first[v];
    e[ecnt].v = u;
    e[ecnt].u = v;
    e[ecnt].id = c;
    first[v] = ecnt++;
}

struct cmp{
    bool operator ()(pii a,pii b){
        return a.first > b.first;
    }
};

void Dijstra1(int s){
    priority_queue<pii,vector<pii >,cmp> PQ;
    dis1[s] = 0;
    PQ.push(MP(dis1[s],s));
    int cnt = 0;
    while(!PQ.empty()){
        pii x = PQ.top(); PQ.pop();
        if(dis1[x.second] < x.first) continue; 
        for(int i = first1[x.second]; i != -1; i = nxt1[i]){
            int v = e1[i].v;
            if(dis1[v] > dis1[x.second] + e1[i].cost){
                dis1[v] = dis1[x.second] + e1[i].cost;
                PQ.push(MP(dis1[v],v));
            }
        }
    }
}

void Dijstra2(int s){
    priority_queue<pii,vector<pii >,cmp> PQ;
    dis2[s] = 0;
    PQ.push(MP(dis2[s],s));
    int cnt = 0;
    while(!PQ.empty()){
        pii x = PQ.top(); PQ.pop();
        if(dis2[x.second] < x.first) continue; 
        for(int i = first2[x.second]; i != -1; i = nxt2[i]){
            int v = e2[i].v;
            if(dis2[v] > dis2[x.second] + e2[i].cost){
                dis2[v] = dis2[x.second] + e2[i].cost;
                PQ.push(MP(dis2[v],v));
            }
        }
    }
}


void Dfs(int p,int pre){
    dfn[p] = low[p] = ++tot;
    for(int i = first[p]; ~i; i = nxt[i]){
        int v = e[i].v;
        if(vis[i]) continue;
        vis[i] = vis[i ^ 1] = true;
        if(!dfn[v]){
            Dfs(v,p);
            low[p] = min(low[p],low[v]);
            if(low[v] > dfn[p]) {
                bg[i] = bg[i ^ 1] = true;
                ans[e[i].id] = 1;
            }
        }
        else low[p] = min(low[p],dfn[v]);
    }
}

void Tarjan(){
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(bg,false,sizeof(bg));
    memset(vis,false,sizeof(vis));
    tot = 0;
    for(int i = 1; i <= N; ++i) if( dfn[i] == 0) Dfs(i,-1);
}

void solve(){
    memset(res,-1,sizeof(res));
    for(int i = 1;i <= M;i++){
        int u = e1[i].u;
        int v = e1[i].v;
        if(ans[i] == 1) {
            res[i] = 0;
            continue;
        }
        ll need = path - dis1[u] - dis2[v];
        if(need > 1){
             res[i] = e1[i].cost - need + 1;
        }
    }
    
    
    for(int i = 1;i <= M;i++){
        if(res[i] == 0) puts("YES");
        else if(res[i] == -1) puts("NO");
        else printf("CAN %d
",res[i]);
    }
}

int main(){
    int a,b,c,s,t;
    num = 0;
    while(scanf("%d%d%d%d",&N,&M,&s,&t) != EOF){
        num++;
        init();
        int x;
        
        for(int i = 1; i <= M; ++i){
            scanf("%d%d%d",&a,&b,&c);
            Add_edge1(a,b,c);
            Add_edge2(b,a,c);
        }
        
        for(int i = 1;i <= N;i++) dis1[i] = dis2[i] = 1ll << 50;
        
        Dijstra1(s);
        Dijstra2(t);
        path = dis1[t];
       
        for(int u = 1;u <= N;u++){
            for(int i = first1[u];~i;i = nxt1[i]){
                int v = e1[i].v;
                if(dis1[u] + dis2[v] + e1[i].cost == path) {
                    e1[i].tag = 1;
                    e2[i].tag = 1;
                    Add_edge(u,v,i);
                }
            }
        }
        
        memset(ans,0,sizeof(ans));
        Tarjan();        
        solve();
    }
    return 0;
}