单源最短路径1题解

特蕾西娅~

2025-07-25 18:07:31

发布于：浙江

3阅读

0回复

0点赞

单源最短路径1

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const int INF = 0x3f3f3f3f;
int dis[N],vis[N],mp[N][N],n,m,s;
void dijkstra(){
    // 读入边并处理重边（取最小值）    
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        if(w<mp[u][v])mp[u][v]=w;
    }
    // Dijkstra 初始化    
    dis[s]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    q.push({0,s});
    while(!q.empty()){
        int u = q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int v = 1;v <= n;v++){
            if(mp[u][v]!=INF&&dis[v]>dis[u]+mp[u][v]){
                dis[v]=dis[u]+mp[u][v];
                q.push({dis[v],v});
            }
        }
    }
}
int main(){
    // 初始化邻接矩阵和最短距离
    memset(mp,0x3f,sizeof(mp));
    fill(dis,dis+1010,INF);
    cin>>n>>m>>s;
    dijkstra();
    // 输出结果    
    for(int i = 1;i <= n;i++){
        if(dis[i]==INF)cout<<-1<<" ";
        else cout<<dis[i]<<" ";
    }
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论