dijkstra模板

某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。

现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
Input
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
Output
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<string>

using namespace std;

const int MAX=pow(2,31)-1;
class Node
{
public:
    int dist;
    bool isinspected;
    Node(){dist=MAX,isinspected=false;}
};
int road[205][205];
inline void initate(int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            road[i][j]=MAX;
    }
}
int main()
{
    int n,m,k=0;
    while((scanf("%d %d",&n,&m))!=EOF)//n个城镇，m个道路
    {
        int num=0;
        Node minpath[205];
        initate(n);
        int a,b,x;
        for(int i=0;i<m;i++)
        {
            scanf("%d %d %d",&a,&b,&x);
            if(road[a][b]>x&&a!=b)
            {
            road[a][b]=x;
            road[b][a]=x;
            }
        }
        int begin,end;
        scanf("%d %d",&begin,&end);
        minpath[begin].dist=0;
        while(1)
        {
            num++;
            if(num==4)
            k++;
            int minp=MAX,minindex;
            bool isfound=false;
        for(int i=0;i<n;i++)
        {
            if(!minpath[i].isinspected)
            {
            if(minp>minpath[i].dist)
            {
            minp=minpath[i].dist;
            minindex=i;
            isfound=true;
            }
            }
        }
        if(!isfound)
        break;
        minpath[minindex].isinspected=true;
        for(int i=0;i<n;i++)
        {
            if(minpath[i].isinspected==false&&road[minindex][i]!=MAX)
            minpath[i].dist=min(minpath[i].dist,minp+road[minindex][i]);
        }
        /*cout<< "第" << num << "次 ";
        for(int i = 0; i < n; i++)
        {
        cout<<minpath[i].dist << " ";
        }
        cout<< endl;*/
        }
        if(minpath[end].dist==MAX)
        printf("-1\n");
        else
        printf("%d\n",minpath[end].dist);
    }
    getchar();
    getchar();
}

注释版代码
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的女装。所有

同学都迫不及待的想穿上女装！所以现在负责搬运女装的工作人员想要寻

找最短的从商店到赛场的路线，你可以帮助他们吗？

input

输入包括多组数据。每组数据第一行是两个整数M、N（M<=100，N<=10000）

，N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的

路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来

M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A

与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。输入保

证至少存在1条商店到赛场的路线。

output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

#include<iostream>
#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;

const int MAX = pow(2,31)-1;//人工定义无穷大


class Node {
public:
    int dist;
    int path;
    bool isinspect;
    Node(){ dist = MAX, path = -1,isinspect=false; };
};

////////数组的下标和实际定义的意义相差1/////////
int main()

{

    int k = 0,num=0,start,end,totallength;
    bool isfound = false;
    int x, y,numpath;
    int M, N;//M<=100 节点数,N<=10000 路径数
    while(1)
    {
    scanf("%d%d",&M, &N);
    start= 1, end = M;
    if(M == 0)
    break;
    vector<Node> minpath;
    minpath.resi***t picture[105][105];
    //vector<vector<int>> picture(M,vector<int>());//初始化picture M*M
    //for(int i = 0; i < M; i++)
    //picture[i].resize(M,MAX);//初始化路径
    for(int i=0;i<=100;i++)
    {
        for(int j=0;j<=100;j++)
        picture[i][j]=MAX;
    }
    for(int i = 0; i < N; i++)//读入图
    {
    scanf("%d%d%d",&x, &y, &numpath);
    if(numpath < picture[x - 1][y - 1]&&x!=y)
    {
    picture[x- 1][y - 1] = numpath;
    picture[y- 1][x - 1] = numpath;
    }
    }
    int minindex;//未检测过的，最小dist的节点
    minpath[start-1].dist= 0;//将起点的dist置零，保证第一个找到的minindex=1
    while(1)
    {
    num++;
    isfound= false;
    for(int i = 1, min = MAX; i <= M; i++)
    {
    //找出minpath中dist最小的节点
    if(minpath[i - 1].isinspect == false && min > minpath[i - 1].dist)//没被检测过且是最小的
    {
    min= minpath[i - 1].dist;
    minindex= i;
    isfound= true;
    }
    }
    if(isfound == false)//全部检测过，退出
    break;
    minpath[minindex-1].isinspect= true;//被检测过了,minindex表示当前源，destination表示目的地
    for(int desination = 1; desination <= M; desination++)
    {
    if(minpath[desination - 1].isinspect == false)//如果没被检测过
    {
    if(picture[minindex - 1][desination - 1] != MAX)//如果是连通的
    {
    //if(num == 2 && desination == 2)
    //cout<< minpath[minindex - 1].dist << " " <<picture[minindex - 1][desination - 1] << endl;
    totallength= minpath[minindex-1].dist + picture[minindex - 1][desination - 1];
    if(minpath[desination - 1].dist > totallength)       //若现在的节点的dist大于totallength，更新
    {
    minpath[desination- 1].dist = totallength;
    minpath[desination- 1].path = minindex;
    }
    }
    }
    }
     //////debug代码///////
    /*cout<< "第" << num << "次 ";
    for(int i = 1; i <= M; i++)
    {
    cout<<minpath[i- 1].dist << " ";
    }
    cout<< endl;*/
    }
    cout<< minpath[end - 1].dist << endl;
    }

}