九度 1411 -图最短路径

这道题目检查对于dijkstra算法的掌握，假设对于这个算法有疑问的，能够看看这个博客点击打开链接。基本上已经讲得非常清楚了。

这道题目的细节有:1：在给的有向图中。一条边会反复，所以我们要选最小的那条覆盖 2:有s-s的边。

大家做的时候要小心这两个细节。

dijkstra算法代码总体模板就是这个博客点击打开链接的。

#include<iostream>
#include<string.h>
#define MAX 10000000
using namespace std;
int map[510][510];
int sp[510];
int s[510];
 
int n,x,y;
void djs(){
    for(int i=1;i<=n;i++){
        sp[i]=MAX;s[i]=0;
    }
    int init=x,count=0;
    int mv,mi;
    for(int i=1;i<=n;i++){
        if(map[x][i]<sp[i])sp[i]=map[x][i];
    }
    while(count++<=n){
        mv=MAX+1, mi=-1;
        for(int i=1;i<=n;i++){
            if(!s[i]){
                if(map[init][i]+sp[init]<sp[i])sp[i]=map[init][i]+sp[init];
                if(sp[i]<mv){
                    mv=sp[i];mi=i;
                }   
            }
        }
        s[mi]=1;init=mi;
    }
    if(sp[x]==MAX){
        cout<<"help!"<<endl;
    }
    else{
        cout<<sp[x]<<endl;
    }
}
int main(){
     
    int m;
    int a,b,t;
    while(cin>>n>>m>>x){
        memset(map,1,sizeof(map));
        for(int i=0;i<m;i++){
            cin>>a>>b>>t;
            map[a][b]=min(t,map[a][b]);
        }
        djs();
    }
}