wpy的请求
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
“题目名称只是吸引你来做题的啦，其实和题目没什么卵关系：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<=103，m<=3*103，|w|<=109 数据保证有解，保证没有负环，保证任意两点间最短路唯一,保证图联通 数据有梯度（
但是出题人也不知道能写什么部分分）
题解：
所有边加相同值变正肯定不行，具体看官方题解第一段
其实想明白就不难
先说结论：建立一个超级源点与每个节点相连，边权为0，然后从超级源点跑spfa，对于u到v边权为w的边，新边权为dis[u]-dis[v]+w
原理：
spfa中更新最短路径的关键是：dis[v]>=dis[u]+w
当满足这个条件时，路径就可以更新。而当路径为最短路时，也就有dis[u]+w-dis[v]>=0成立
我们再看看点u到v的最短路径为u->x->y->v
那么最短路径长度就是：dis（u，x）+dis（x，y）+dis（y，v）
dis（u，x）表示u到x的最短路径
现在我们要更改边权，（因为边权值可能为负数），使得单个边权的值>=0，
dis[u]+w-dis[v]>=0,w就相当于dis（u，x）,我们带入得到：
dis[u]-dis[x]+dis[x]-dis[y]+dis[y]-dis[v]+dis（u，x）+dis（x，y）+dis（y，v）
化简得：
dis（u，x）+dis（x，y）+dis（y，v）+dis[u]-dis[v]
dis[u]-dis[v]是定值
前面三个就是原路径的w，这不就是我们一开始说的结论
代码：
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
struct node
{
int to,next,w,u;
}edge[100005];
long long head[10005],tot=0,vis[10005],dis[10005];
void add(int u,int v, int w)
{
edge[++tot].to=v;
edge[tot].w=w;
edge[tot].u=u;
edge[tot].next=head[u];
head[u]=tot;
}
void spfa()
{
memset(dis,inf,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(0);
dis[0]=0;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u]; i ;i=edge[i].next){
int v=edge[i].to,w=edge[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
}
int main ()
{
int T,i,t,j,k,p,sum=0,v,u,w;
cin>>n>>m;
for(i=0;i<m;++i){
cin>>u>>v>>w;
add(u,v,w);
}
for(i=1;i<=n;++i)
add(0,i,0);
spfa();
for(i=1;i<=m;++i){
u=edge[i].u; v=edge[i].to; w=edge[i].w;
printf("%d %d %d\n",u,v,dis[u]-dis[v]+w);
}
return 0;
}
京公网安备 11010502036488号