Complete the Graph

题目描述

ZS the Coder has drawn an undirected graph of $n$ vertices numbered from $0$ to $n-1$ and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.
The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices $s$ and $t$ in the resulting graph is exactly $L$. Can you help him?

代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
long long n, m, L, s, t, dist[1001], line[1001][1001];
bool flag, in[1001], sign[1001][1001];
void spfa(int p = -1, int q = -1) {
queue<int> que;
while (!que.empty()) que.pop();
memset(in, false, sizeof(in));
if (p == -1) {
memset(dist, 0x1f, sizeof(dist));
que.push(s), dist[s] = 0, in[s] = true;
} else {
if (dist[p] > dist[q]) p ^= q ^= p ^= q;
que.push(p), in[p] = true;
}
while (!que.empty()) {
long long u = que.front();
que.pop();
in[u] = false;
for (int i = 0; i < n; ++i) {
if (line[u][i] && dist[i] > dist[u] + line[u][i]) {
dist[i] = dist[u] + line[u][i];
if (!in[i]) que.push(i), in[i] = true;
}
}
}
}
int main()
{
cin >> n >> m >> L >> s >> t;
for (int i = 1; i <= m; ++i) {
long long x, y, w;
cin >> x >> y >> w;
line[x][y] = line[y][x] = w;
if (!w) sign[x][y] = sign[y][x] = true;
}
spfa();
if (dist[t] < L) {
cout << "NO" << endl;
return 0;
} else if (dist[t] > L) {
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (sign[i][j]) {
line[i][j] = line[j][i] = 1;
sign[i][j] = sign[j][i] = false;
spfa(i, j);
if (dist[t] <= L) {
line[i][j] = line[j][i] = L - dist[t] + 1;
flag = true; break;
}
}
}
if (flag) break;
}
} else flag = true;
if (!flag) cout << "NO" << endl;
else {
cout << "YES" << endl;
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (line[i][j] || sign[i][j]) {
cout << i << ' ' << j << ' ';
if (line[i][j]) cout << line[i][j];
if (sign[i][j]) cout << (long long) 1e18;
cout << endl;
}
}
}
}
return 0;
}


418 I'm a teapot