Codeforces Round #372 (Div. 1) B. Complete The Graph

,

http://codeforces.com/contest/715/problem/B

提出前にちゃんと確認しなかったためにpretestで$2$WA生やしたし、間違ったassertが混入しててWAになった。つらい。

solution

Dijkstra on $(\rm{erased}, \rm{dist})$.

Find the path $P$, which the $(k, d)$ is minimum in paths which $k + d \le L$ holds ($k$ is the shortest number of erased edges on the path, $d$ is the distance). Then, assign weights to erased edges on $P$. While $\rm{distance}(P) = L$ holds, any assignment is possible. For the other erased edges, assign large number like $10^{18}$. If you cannot $\rm{distance}(P) = L$, it’s the case $k = 0 \land d \lt L$ or there is no such $P$, the answer is NO.

If the $(k, d)$ is minimal, any assignment for erased edges on $P$ doesn’t make a path $Q$ which $\rm{distance}(Q) \lt \rm{distance}(P)$.

implementation

#include <cstdio>
#include <vector>
#include <queue>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); }
struct edge_t { int u, v, w, i; };
struct state_t { int v, erased; ll dist; int edge; };
bool operator < (state_t const & a, state_t const & b) { return make_pair(- a.erased, - a.dist) < make_pair(- b.erased, - b.dist); } // weak
const ll inf = 1e18;
int main() {
    // input
    int n, m, len, src, dst; scanf("%d%d%d%d%d", &n, &m, &len, &src, &dst);
    vector<vector<edge_t> > g(n);
    vector<edge_t> edges(m);
    repeat (i,m) {
        edge_t e; scanf("%d%d%d", &e.u, &e.v, &e.w); e.i = i;
        edges[i] = e;
        g[e.u].push_back(e);
        swap(e.u, e.v);
        g[e.u].push_back(e);
    }
    // compute
    vector<vector<ll> > dist = vectors<ll>(inf, n, n+1);
    vector<vector<int> > from = vectors<int>(-1, n, n+1);
    priority_queue<state_t> que;
    que.push((state_t) { src, 0, 0ll, -1 });
    int erased = -1;
    while (not que.empty()) {
        state_t a = que.top(); que.pop();
        if (dist[a.v][a.erased] != inf) continue;
        dist[a.v][a.erased] = a.dist;
        from[a.v][a.erased] = a.edge;
        if (a.v == dst) {
            erased = a.erased;
            break;
        }
        for (edge_t e : g[a.v]) {
            state_t b = { e.v, a.erased + (e.w == 0), a.dist + e.w, e.i };
            if (b.erased > n) continue;
            if (dist[b.v][b.erased] != inf) continue;
            if (b.dist + b.erased > len) continue;
            que.push(b);
        }
    }
    if (erased == 0 and dist[dst][erased] < len) {
        erased = -1;
    }
    if (erased != -1) {
        int v = dst;
        int k = erased;
        int l = len;
        while (from[v][k] != -1) {
            int i = from[v][k];
            int u = (v == edges[i].v ? edges[i].u : edges[i].v);
            if (edges[i].w) {
                l -= edges[i].w;
            } else {
                if (k == 1) {
                    edges[i].w = l - dist[u][0];
                } else {
                    edges[i].w = 1;
                    l -= 1;
                }
                k -= 1;
            }
            v = u;
        }
    }
    // output
    if (erased == -1) {
        printf("NO\n");
    } else {
        printf("YES\n");
        for (edge_t e : edges) {
            ll w = e.w ? ll(e.w) : inf;
            printf("%d %d %lld\n", e.u, e.v, w);
        }
    }
    return 0;
}