Dijskra最短路径

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int mp[N][N];
int n,s;
int dist[N];
bool st[N];
typedef pair<int,int> PII;

void dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;
    priority_queue<PII,vector<PII>,greater<PII> >heap;
    heap.push({0,s});
    while(heap.size()){
        auto t=heap.top();
        heap.pop();
        int ver=t.second,dis=t.first;
        if(st[ver])    continue;
        st[ver]=1;
        for(int i=1;i<=n;i++){
            if(mp[ver][i]){
                if(dist[i]>dis+mp[ver][i]){
                    dist[i]=dis+mp[ver][i];
                    heap.push({dist[i],i});
                }
            }
        }
    }
    
}
int main(){
    
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            
            scanf("%d ",&mp[i][j]);
            //cin>>mp[i][j];
            //if(mp[i][j]=='-')   mp[i][j]=0;
        }
    }
    
    dijkstra();
    for(int i=1;i<=n;i++){
        if(i==s)    continue;
        
        printf("(%d -> %d) = %d\n",s,i,dist[i]);
    }
    
}