【题解】旅行
题目描述
给你一张无重边无自环的带权无向图，给予起点S = 1。蓝蓝本来是想让你求出S到所有其他点的最短路，可是淘淘说这个太简单了，于是他给出了加强版。 给出的无向图保证S到任何点的最短路是唯一的，但是有一个限制：当从S到任意一点T时，此条最短路的第一条边不允许通过。在满足限制的条件下，求S到其它所有点最短路的长度。数据保证每个点都有解
输入格式
一行n,m。接下来m行，每行u,v,w三个数，表示有一条长度为w的无向边连接u和v。
输出格式
输出n – 1行，第i行表示S到i + 1的在满足限制的条件下最短路长度。
输入输出样例
输入 #1
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3输出 #1
3
3
6说明/提示
对于50\%的数据，n \le 20
对于70\%的数据，n \le 100
对于另外10\%，只有两种边权。
对于100\%的数据，n \le 300, m \le 400
分析
首先在全图跑一遍dijkstra，建立一个数组a以记录从1开始到当前点s的最短路所经过的第一条边是(1,a[s])，然后我们只需要删掉这条边，在全图再针对每个点跑一遍dijkstra即可得到答案。
注意题面有误，数据存在重边。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,mp[301][301],dis[301],a[301],vis[301],tmp;
void dij_init(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
for(int i=2;i<=n;i++){
dis[i]=mp[1][i];
}
for(int i=1;i<n;i++){
int x=0;
for(int j=2;j<=n;j++){
if(vis[j])continue;
if(dis[j]<dis[x]||x==0)x=j;
}
vis[x]=1;
for(int y=1;y<=n;y++){
if(dis[x]+mp[x][y]<dis[y]){
a[y]=a[x];
dis[y]=dis[x]+mp[x][y];
}
}
}
}
void dij(int s){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
tmp=mp[1][a[s]];
mp[1][a[s]]=mp[a[s]][1]=0x3f3f3f3f;
for(int i=2;i<=n;i++){
dis[i]=mp[1][i];
}
for(int i=1;i<n;i++){
int x=0;
for(int j=2;j<=n;j++){
if(vis[j]){
continue;
}
if(dis[j]<dis[x]||x==0)x=j;
}
vis[x]=1;
for(int y=1;y<=n;y++){
if(dis[x]+mp[x][y]<dis[y]){
dis[y]=dis[x]+mp[x][y];
}
}
}
}
signed main(){
memset(mp,0x3f,sizeof(mp));
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
mp[u][v]=mp[v][u]=min(w,mp[u][v]);
if(u==1)a[v]=v;
if(v==1)a[u]=u;
}
dij_init();
for(int i=2;i<=n;i++){
if(i>2)mp[1][a[i-1]]=mp[a[i-1]][1]=tmp;
dij(i);
printf("%lld\n",dis[i]);
}
return 0;
}最后修改：2021 年 07 月 06 日 08 : 50 PM
© 允许规范转载
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021 年 07 月，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
