题目
题目描述
“题目名称只是吸引你来做题的啦，其实和题目没什么卵关系：o(*￣▽￣*)o” —— 历史——殿堂
wpy移情别恋啦，他不喜欢spfa了，现在他喜欢使用dij，但是他又发现了一个新的问题，dij无法跑有负权边的图，于是wpy找到了她的男朋友也就是你来帮忙，为了你晚上的幸福生活，你必须在1秒内帮她解决这个问题，然后蹿到床上。。。balabala（捂脸）。。。。(*/ω＼*)
简单来说，有一张n个点，m条边的有向图，请你给每条边确定一个新的边权（不同边之间可以不同），保证对于任意u，v，在新图上的u到v的最短路上的点和原图上最短路上的点相同且顺序不变。
新的边权要求非负。
输入描述
第一行两个整数n,m,表示有n个点，m条边。
接下来m行，每行三个数，u，v，w，表示有一条从u到v。
输出描述
输出m行，每行三个整数u,v,w表示有从u到v的边边权改完后是为w。
ps：按输入顺序输出。
示例1
输入
5 10
1 2 -4383
1 3 -9930
2 4 -7331
1 5 -2175
2 3 11962
2 5 16382
4 5 11420
1 4 37978
3 5 13836
3 4 14617
输出
1 2 0
1 3 0
2 4 0
1 5 0
2 3 17509
2 5 14174
4 5 1881
1 4 49692
3 5 6081
3 4 16401
备注
\(n<=10^3，m<=3*10^3，|w|<=10^9\)
数据保证有解，保证没有负环，保证任意两点间最短路唯一,保证图联通
数据有梯度（ 但是出题人也不知道能写什么部分分）
题解
知识点：最短路，数学。
这道题利用了最短路不等式：对于任意边 \(u \to v\) 边权为 \(w\) ，都有 \(dis[v] \leq dis[u] + w\) （因为最短路满足了 \(dis[v]>dis[u]+w\) 必然更新，因此最后一定满足这个不等式）。于是，我们有 \(dis[u]-dis[v]+w \geq 0\) 恒为正。
题目要求我们将边权都改成正的且不影响最短路。换句话说，对于任意相同两个点 \(u,v\) ，我们需要在不改变其所有路径的权值的相对大小的情况下，要让边权都改为正的。因此，边在改正之后的影响，只能等价于对所有路径同时加一个常量。我们猜测将所有路径改为 \(dis[u]-dis[v]+w\) 。
对于 \(u,v\) 的任意路径 \(u \to x_1 \to x_2 \to \cdots \to x_n \to v\) 的权值和为 \(w = w(u,x_1) + \cdots + w(x_n,v)\) 。若改变边权后，则整条路径的权值和变为 \(dis[u] - dis[x_1] + w(u,x_1) + \cdots + dis[x_{n}]-dis[v] + w(x_n,v) = dis[u]-dis[v] + w\) ，即 \(u,v\) 的任意路径都加了常量 \(dis[u] - dis[v]\) ，所有路径的权值相对不变，即保证了最短路不变，并且所有边权都为正。 因此，我们把所有边权改为 \(dis[u]-dis[v] + w\) 即可。
注意，建一个超级源点，保证每个点都有最短路。否则，有可能从单源点没法走到某些点。
时间复杂度 \(O((n+m) \log m)\)
空间复杂度 \(O(n+m)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
template<class T>
struct Graph {
struct edge {
int v, nxt;
T w;
};
int idx;
vector<int> h;
vector<edge> e;
Graph(int n, int m):idx(0), h(n + 1), e(m + 1) {}
void init(int n) {
idx = 0;
h.assign(n + 1, 0);
}
void add(int u, int v, T w) {
e[++idx] = edge{ v,h[u],w };
h[u] = idx;
}
};
///链式前向星（有权），空间复杂度O(n+m)，空间性能最优，时间性能较好，使用较复杂
const int N = 1000 + 7, M = 3000 + 1000 + 7;
Graph<int> g(N, M);
int n, m;
bool vis[N];
ll dis[N];
queue<int> q;
void SPFA(int st) {
for (int i = 1;i <= n + 1;i++) dis[i] = 0x3f3f3f3f3f3f3f3f;
dis[st] = 0;
q.push(st);
vis[st] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = g.h[u];i;i = g.e[i].nxt) {
int v = g.e[i].v, w = g.e[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
vector<tuple<int, int, int>> ans;
for (int i = 1;i <= m;i++) {
int u, v, w;
cin >> u >> v >> w;
g.add(u, v, w);
ans.push_back({ u,v,w });
}
for (int i = 1;i <= n;i++) g.add(n + 1, i, 0);
SPFA(n + 1);
for (auto [u, v, w] : ans) {
cout << u << ' ' << v << ' ' << w + dis[u] - dis[v] << '\n';
}
return 0;
}