Codeforces715 B. Complete The Graph

传送门：>Here<

解题思路

　　注意是最短路是L，而非存在一条路径为L。并且边权为0的边必须变为正整数，最小也得是1

　　这题由于n=1000，所以可以稍微暴力一点……

　　首先，先不加任何一条为0的边跑Dij，如果此时的最短路已经$< L$，那么后面的边无论怎么加都不会使最短路比当前的大了，因此无解

　　此时最短路$\geq L$。然后考虑一条一条把边加进图里。每一条塞进图里的边权值都设为最小（也就是1）。如果加上了当前这条边使得最短路$< L$了，那么导致最短路变小的一定就是当前这一条边。因为除了通过当前这条边的路径以外其他路径都$\geq L$。所以我们可以修改这一条边的权值为$L-d[t]+1$，也就是把最短路凑成等于L。并且修改之后所有的路径依然$\geq L$。如果加上当前这一条边最短路依然$\geq L$，那么这条边就是废掉的，可以不管。所以我们需要做的，就是对于每一条使最短路$< L$的边都做此修改。最后判断最短路是否等于L即可。复杂度$O(m^2\ log\ n)$，非常巧妙~

Code

　　注意应当把无法使路径变小的边权值设为1

/*By DennyQi*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

#define  r  read()

#define  Max(a,b)  (((a)>(b)) ? (a) : (b))

#define  Min(a,b)  (((a)<(b)) ? (a) : (b))

#define  ERR   {puts("NO");return 0;}

using namespace std;

typedef long long ll;

#define int long long

const int MAXN = ;

const int MAXM = ;

const int INF = 1e13;

inline int read(){

    int x = ; int w = ; register int c = getchar();

    while(c ^ '-' && (c < '' || c > '')) c = getchar();

    if(c == '-') w = -, c = getchar();

    while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar(); return x * w;

}

struct Edge{

    int u,v,w;

}a[MAXM];

struct Node{

    int idx,w;

};

inline bool operator < (const Node& a, const Node& b){

    return a.w > b.w;

}

int N,M,L,S,T,x,y,z;

int first[MAXM*],nxt[MAXM*],to[MAXM*],cost[MAXM*],num_edge;

priority_queue <Node> q;

int d[MAXN],vis[MAXN];

inline void add(int u, int v, int w){

    to[++num_edge] = v;

    cost[num_edge] = w;

    nxt[num_edge] = first[u];

    first[u] = num_edge;

}

inline void Dijkstra(int s){

    for(int i = ; i <= N; ++i) d[i] = INF;

    memset(vis, , sizeof(vis));

    d[s] = ;

    q.push((Node){s, });

    int u, v;

    while(!q.empty()){

        u = q.top().idx; q.pop();

        if(vis[u]) continue; vis[u]=;

        for(int i = first[u]; i; i = nxt[i]){

            v = to[i];

            if(d[u] + cost[i] < d[v]){

                d[v] = d[u] + cost[i];

                q.push((Node){v,d[v]});

            }

        }

    }

}

main(){

//    freopen(".in","r",stdin);

    N=r,M=r,L=r,S=r,T=r;

    for(int i = ; i <= M; ++i){

        a[i].u=r, a[i].v=r, a[i].w=r;

        if(a[i].w != ){

            add(a[i].u,a[i].v,a[i].w);

            add(a[i].v,a[i].u,a[i].w);

        }

    }

    Dijkstra(S);

    if(d[T] < L) ERR;

    for(int i = ; i <= M; ++i){

        if(a[i].w != ) continue;

        a[i].w = ;

        add(a[i].u,a[i].v,);

        add(a[i].v,a[i].u,);

        Dijkstra(S);

        if(d[T] < L){

            a[i].w =  - d[T] + L;

            cost[num_edge-] =  - d[T] + L;

            cost[num_edge] =  - d[T] + L;

        }

    }

/*    for(int i = 1; i <= M; ++i){

        printf("%d %d %d\n", a[i].u,a[i].v,a[i].w);

    }

    printf("d[%d] = %d\n",T,d[T]);*/

    Dijkstra(S);

    if(d[T] != L) ERR;

    puts("YES");

    for(int i = ; i <= M; ++i){

        printf("%lld %lld %lld\n", a[i].u,a[i].v,a[i].w);

    }

    return ;

}