Codeforces Round #372 (Div. 1) B. Complete The Graph （枚举+最短路）

题目就是给你一个图，图中部分边没有赋权值，要求你把无权的边赋值，使得s->t的最短路为l。

卡了几周的题了，最后还是经群主大大指点……做出来的……

思路就是跑最短路，然后改权值为最短路和L的差值，直到最短路为L，或者每条无权边都赋值为止。

点是0～n-1的，因为这个错了好几次= =

dijkstra超时，spfa卡过。

看到很多题解说二分，但是实在不能理解那个思路阿…………

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ;

const ll INF = 1e13+;

int n, m, l, s, t;

struct edge { int from, to, next, w; } e[N*N];

int head[N], cntE;

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

    e[cntE].from = u; e[cntE].to = v; e[cntE].next = head[u]; e[cntE].w = w; head[u] = cntE++;

    e[cntE].from = v; e[cntE].to = u; e[cntE].next = head[v]; e[cntE].w = w; head[v] = cntE++;

}

int cnt[N], pre[N];

ll d[N];

bool inq[N];

int spfa() {

    queue<int> q;

    memset(inq, , sizeof inq);

    memset(cnt, , sizeof cnt);

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

    d[s] = ;

    inq[s] = true;

    q.push(s);

    while (q.size()) {

        int u = q.front(); q.pop();

        inq[u] = false;

        for (int i = head[u]; ~i; i = e[i].next) {

            int v = e[i].to;

            int c = e[i].w;

            if (d[u] < INF && d[v] > d[u] + c) {

                d[v] = d[u] + c;

                pre[v] = u;

                if (!inq[v]) {

                    q.push(v); inq[v] = true;

                }

            }

        }

    }

    return d[t];

}

vector<int> zeroedge;

int main()

{

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

    while (~scanf("%d%d%d%d%d", &n, &m, &l, &s, &t)) {

        memset(head, -, sizeof head); cntE = ; zeroedge.clear();

        int u, v, c;

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

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

            addedge(u, v, c==?:c);

            if (c == ) zeroedge.push_back(cntE-);

        }

        ll tmp = spfa();

        if (tmp > l) {

            puts("NO");

            continue;

        }

        if (tmp == l) { // may be dont have zero edge

            puts("YES");

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

                printf("%d %d %d\n", e[i].from, e[i].to, e[i].w);

            }

            continue;

        }

        int fg = false;

        for (int i = ; i < zeroedge.size(); ++i) {

            int x = zeroedge[i];

            e[x].w = e[x ^ ].w = l - tmp + ;

            tmp = spfa();

            if (tmp == l) {

                fg = true;

                puts("YES");

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

                    printf("%d %d %d\n", e[i].from, e[i].to, e[i].w);

                }

                break;

            }

        }

        if (!fg) puts("NO");

    }

    return ;

}