CodeForces 715B Complete The Graph 特殊的dijkstra

Complete The Graph

题解：

比较特殊的dij的题目。

dis[x][y] 代表的是用了x条特殊边， y点的距离是多少。

然后我们通过dij更新dis数组。

然后在跑的时候，把特殊边都先当做1在跑，并且经过特殊边的时候，记得将x更新。

然后如果dis[0][t] < L 则代表不用特殊边也会小于L。所以无论是特殊的边答案是多少，dis[0][t]<L也是固定的。

然后我们不断检查dis[c][t] (for c 1 to N) 是不是 <= L 。

找到对应的dis[c][t]之后， 把最短路上的特殊边更新成符合答案的值。 其他特殊边更新成L+1。

代码从学长那里学的， 可以说十分像了。

对我来说比较新颖的是， 把边初始值赋值为L+1，这样就可以在int的范围内跑完全程的dij了， 毕竟如果路径长度 > L 之后就没必要再跑了。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 1e3 + ;

const int M = 2e4 + ;

int n, m, L, s, t;

int head[N], to[M], val[M], nt[M], tot;

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

    to[tot] = v;

    val[tot] = w;

    nt[tot] = head[u];

    head[u] = tot++;

}

int dis[N][N];

pll pre[N][N];

typedef tuple<int,int,int> tup;

priority_queue<tup, vector<tup>, greater<tup> > pq;

bool dij(){

    for(int i = ; i < N; ++i)

        fill(dis[i], dis[i] + N, L+);

    dis[][s] = ;

    pq.push(tup(,,s));

    /// dis , 0-edge, now-point

    while(!pq.empty()){

        int dd, c, u;

        tie(dd, c, u) = pq.top();

        pq.pop();

        if(dd != dis[c][u]) continue;

        for(int i = head[u]; ~i; i = nt[i]){

            int v = to[i];

            int w = dd + val[i] + (!val[i]);

            int nc = c + (!val[i]);

            if(nc >= N) continue;

            if(dis[nc][v] > w){

                dis[nc][v] = w;

                pq.push(tup(w, nc, v));

                pre[nc][v] = pll(u, i);

            }

        }

    }

    if(dis[][t] < L) return false;

    if(dis[][t] == L) return true;

    for(int c = ; c < N; ++c){

        if(dis[c][t] <= L){

            int add = L - dis[c][t];

            int cc = c, now = t;

            while(now != s){

                pll tt = pre[cc][now];

                now = tt.fi;

                if(val[tt.se] == ){

                    val[tt.se] = val[tt.se^] = add + ;

                    add = ;

                    cc--;

                }

            }

            return true;

        }

    }

    return false;

}

int main(){

    memset(head, -, sizeof head);

    scanf("%d%d%d%d%d", &n, &m, &L, &s, &t);

    int u, v, w;

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

        scanf("%d%d%d", &u, &v, &w);

        add(u, v, w);

        add(v, u, w);

    }

    if(dij()){

        puts("YES");

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

            if(val[i] == ) val[i] = L + ;

            printf("%d %d %d\n", to[i], to[i^], val[i]);

        }

    }

    else puts("NO");

    return ;

}