Codeforces Round #372 (Div. 1) B. Complete The Graph
提出前にちゃんと確認しなかったために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;
}