迪杰斯特拉算法是最典型的 单源最短路径算法，用于计算一个节点到其余所有节点的最短路径。（缺点：该算法中不存在负权边）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define MAX 115
#define INF 0x3f3f3f3

int mp[MAX][MAX] , dis[MAX];      //dis用于保存起点到各个点的距离

bool vis[MAX];                     //用于点的判重

void Dijkstra(int n)
{
    int minx,flag = 1;

    for(int i = 1;i <= n;i++)
    {
        dis[i] = mp[1][i];         //记录刚开始起点到各个点的距离
        vis[i] = true;             //刚开始所有的点都是新点
    }

    vis[1] = false;

    for(int i = 1;i <= n;i++)
    {
        minx = INF;
        for(int j = 1;j <= n;j++)
        {
            if(vis[j] && dis[j] < minx)     //选取起点到各个点中最短的那条边而且这个点是新点
            {
                minx = dis[j];
                flag = j;                    //记录位置
            }
        }
        vis[flag] = false;                   //将这个点标记为旧点，因为已经找到从起点到该点的最短路径了

        if(minx == INF) break;//如果所有的点都为旧点，那么最短路径算法也就完成了

        for(int j = 1;j <= n;j++)
        {
            if(vis[j] && (dis[flag] + mp[flag][j] < dis[j]))
                dis[j] = dis[flag] + mp[flag][j];
        }
    }
}
int main()
{
    int n,m,a,b,c;
    while(~scanf("%d%d",&n,&m))
    {
        if(n == 0 && m == 0) break;

        for (int i=1;i<=MAX;i++)
            for (int j=1;j<=MAX;j++)
                mp[i][j]=INF;                  ///重新设为最大值

        for(int i = 1;i <= m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            mp[a][b] = mp[b][a] = c;//代表点a到点b的距离为c
        }

        Dijkstra(n);

        cout << dis[n] << endl;
    }
    return 0;
}