题目描述
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?
题意概述
给定一张连通无向图，其中所有边的权值均为自然数。要求将所有权值为$0$的边的权值变成任意一个不大于$10^{18}$的正整数，使得从$s$到$t$的最短路径的长度为$L$。
数据范围：$2 \le n \le 1000, \; 1 \le m \le 10000, \; 1 \le L \le 10^9, \; 0 \le s, t \le n-1$。
算法分析
首先将权值为$0$的边的权值变成无穷大，求一次最短路，若$s$和$t$之间的距离$dist \lt L$则无解。
若$dist=L$，则已得到可行解。
若$dist \gt L$，枚举初始权值为$0$的边，将它的权值变成$1$，求一次最短路，若$dist \le L$则说明已有可行解，把这条边的权值增加$L-dist$，即得到可行解。若所有初始权值为$0$的边都已枚举且$dist \gt L$，则说明无解。
代码
#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;
}
