【题解】旅行

题目描述

给你一张无重边无自环的带权无向图，给予起点S = 1。蓝蓝本来是想让你求出S到所有其他点的最短路，可是淘淘说这个太简单了，于是他给出了加强版。给出的无向图保证S到任何点的最短路是唯一的，但是有一个限制：当从S到任意一点T时，此条最短路的第一条边不允许通过。在满足限制的条件下，求S到其它所有点最短路的长度。数据保证每个点都有解

输入格式

一行n,m。接下来m行，每行u,v,w三个数，表示有一条长度为w的无向边连接u和v。

输出格式

输出n – 1行，第i行表示S到i 1的在满足限制的条件下最短路长度。

输入输出样例

输入 #1

代码语言：javascript复制

输出 #1

代码语言：javascript复制

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即可得到答案。

注意题面有误，数据存在重边。

代码语言：javascript复制

#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("%lldn",dis[i]);
    }
    return 0;
}

最后修改：2021 年 07 月 06 日 08 : 50 PM

dijkstra

0 人点赞