朴素版迪杰斯特拉

ccj123

2025-01-23 11:30:56

发布于：上海

9阅读

0回复

0点赞

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1005;

int e[maxn][maxn];
int dis[maxn], vis[maxn];

void dij(int n,int s){
    for(int i = 0;i <= n;i++)
        dis[i] = 1e9;
    dis[s] = 0;
    for(int i = 1;i <= n;i++){
        int u = 0;        
        for(int j = 1;j <= n;j++)
            if(!vis[j] && dis[j] < dis[u]) u = j;
        vis[u] = 1;
        for(int j = 1;j <= n;j++){
            if(e[u][j]) {
                int v = j;
                int w = e[u][j];
                if(dis[v] > dis[u] + w)
                    dis[v] = dis[u] + w;
            }
        }
    }
}


int main(){
    int n,m,s;
    cin >> n >> m >> s;
    for(int i = 0;i < m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        int tmp = e[u][v] ? e[u][v] : 1e9;
        e[u][v] = min(tmp,w);
    }
    dij(n,s);
    for(int i = 1;i <= n;i++){
        if(dis[i] != 1e9) cout << dis[i] << ' ';
        else cout << -1 << ' ';
    }
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论