Dijkstra模板

//模板，方便以后查找
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib> 
#include<algorithm>
using namespace std;
const int N=1010,M=2000010,INF=1000000;
 int dis[N],map[N][N],n,m;//dis起始点到各顶点i的距离，map各点连接情况
bool vis[N];
void Init(){　　//初始化
    for(int i=1;i<=n;i++){
        dis[i]=INF;
        vis[i]=false;
        for(int j=1;j<=i;j++)
            i==j?map[i][j]=0:map[i][j]=map[j][i]=INF;
    }
}
int  cmin(int a,int b){
if(a>b)return b;
return a;
}
void Dj(int s){
    dis[s]=0;
    for(int i=1;i<=n;i++){　　　　//　依次选出最短路径的点，总共n-1个　,n次也行
        int p=-1,min=INF;
        for(int j=1;j<=n;j++){　　　//找出最短路径的点以及下标
            if(!vis[j]&&dis[j]<min){
                min=dis[j];
                p=j;
            }
        }
        vis[p]=1;
        for(int j=1;j<=n;j++){　//　更新一下每个点到指定点的最短距离
            if(!vis[j])　　　　
            dis[j]=   cmin(dis[j],(dis[p]+map[p][j]));
        }
    }
}
 
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        Init();
        int q,t;
        cin>>q>>t;
        int x,y,val;
        for(int i=0;i<m;i++){
            cin>>x>>y>>val;
            map[x][y]=map[y][x]=val;　　　//　初始化每个点到指定点的最短路径
        } 
        Dj(q);
        cout<<dis[t]<<endl;
    //    for(int i=1;i<=n;i++)
        //    cout<<dis[i]<<endl;
    }
    return 0;
}