题目描述

给你一张无重边无自环的带权无向图,给予起点$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
如果觉得我的文章对你有用,请随意赞赏