http://acm.hdu.edu.cn/showproblem.php?pid=2544

迪杰斯特拉算法

#include<stdio.h>
#include <string.h>

#define INF 0x3f3f3f
int n, m;
int map[110][110];

void init()   //初始化图，权值无穷大
{
    int i,j;
    for (i=1; i<=n; i++)
        {
            for (j=1; j<=n; j++)
                map[i][j] = INF;
            map[i][i] = 0;
        }
}

void input()
{
    int i;
    int a,b,c;
    for (i=0; i<m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            if (map[a][b]>c)
                map[a][b] = map[b][a] = c;   //无向图
        }
}

void dijkstra()
{
    int i,j,mindis,key;
    int dis[110];   //存放最短路长度(会被更新，不过最后的一定是最短路)
    int used[110];   //标志数组，这个点有最短路了就标记1
    for (i=1; i<=n; i++) //初始化每个点的最短路为INF
        {
            dis[i] = INF;
            used[i] = 0;   //全部点都没找过
        }
    dis[1] = 0;
    while (1)
        {
            mindis = INF;
            key = -1;
            for (i=1; i<=n; i++) //找权(路径)最短的点
                {
                    if (!used[i]&&dis[i]<mindis)
                        {
                            mindis = dis[i];
                            key = i;   //找到了赋值给key
                        }
                }
            if (key==-1||key==n)   //没有路径最短的点了或者找到最后一个点了就结束了
                break;
            used[key] = 1;   //找到了就标记为1
            for (j=1; j<=n; j++) //从key点出发找最短路(权)的点
                {
                    if (!used[j]&&dis[j]>dis[key] + map[key][j])
                        dis[j] = dis[key] + map[key][j];   //修改最短路长度
                }
        }
    printf("%d\n",dis[n]);
}

int main()
{
    while (scanf("%d%d",&n,&m)!

=EOF&&n&&m)
        {
            init();
            input();
            dijkstra();
        }
    return 0;
}