题解 | #公交线路#

最短路模板题

坑点：题目可能会给你重边，只要选最小的一条即可

1、dij算法

#include <bits/stdc++.h>
using namespace std;
int n,m,s,t;
int dis[1010];
bool vis[1010];
int G[1010][1010];
int dij(int s,int t){
    for(int i = 1;i <= n;i++)    //初始化距离表
        dis[i] = G[s][i];
    for(int i = 1;i < n;i++){    
        int Min = 0x3f3f3f3f;
        int index = 0;
        for(int j = 1;j <= n;j++){    //找到当前未被标记的最小边
            if(!vis[j] && dis[j] < Min){
                Min = dis[j];
                index = j;
            }
        }
        vis[index] = 1;    //标记当前边，并确定为最短边
        for(int j = 1;j <= n;j++){
            dis[j] = min(dis[j],G[j][index]+dis[index]);
        }
    }
    return dis[t];
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    memset(dis,0x3f,sizeof(dis));
    memset(G,0x3f,sizeof(G));
    cin>>n>>m>>s>>t;
    while(m--){    //读入图
        int a,b,v;
        cin>>a>>b>>v;
        G[a][b] = min(v,G[a][b]);    //可能会出现重边，选最小的那条
        G[b][a] = min(v,G[b][a]);
    }
    for(int i = 1;i <= n;i++)    //置对角线为0
        G[i][i] = 0;
    int tmp = dij(s,t);
    if(tmp >= 0x3f3f3f3f) cout<<-1;    //若距离为无穷大，则输出-1
    else cout<<tmp;
    return 0;
}

2、bellman ford算法（适用于带负边但不含负环的图）

#include <bits/stdc++.h>
using namespace std;
int n,m,s,t;
int dis[1010];
bool vis[1010];
int G[1010][1010];
int BF(int s,int t){
    for(int i = 1;i <= n;i++)    //初始化距离表
        dis[i] = G[s][i];
    bool flag = true;
    while(flag){
        flag = false;
        for(int i = 1;i <= n;i++){    //对所有能松弛的点都松弛
            for(int j = 1;j <= n;j++){
                if(dis[i] > dis[j] + G[i][j]){
                    dis[i] = dis[j] + G[i][j];
                    flag = true;
                }
            }
        }
    }
    return dis[t];
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    memset(dis,0x3f,sizeof(dis));
    memset(G,0x3f,sizeof(G));
    cin>>n>>m>>s>>t;
    while(m--){    //读入图
        int a,b,v;
        cin>>a>>b>>v;
        G[a][b] = min(v,G[a][b]);    //可能会出现重边，选最小的那条
        G[b][a] = min(v,G[b][a]);
    }
    for(int i = 1;i <= n;i++)    //置对角线为0
        G[i][i] = 0;
    int tmp = BF(s,t);
    if(tmp >= 0x3f3f3f3f) cout<<-1;    //若距离为无穷大，则输出-1
    else cout<<tmp;
    return 0;
}