图结构练习——最短路径

Problem Description

 给定一个带权无向图,求节点1到节点n的最短路径。
 

Input

 输入包含多组数据,格式如下。
第一行包括两个整数n m,代表节点个数和边的个数。(n<=100)
剩下m行每行3个正整数a b c,代表节点a和节点b之间有一条边,权值为c。
 

Output

 每组输出占一行,仅输出从1到n的最短路径权值。(保证最短路径存在)
 

Example Input

3 2
1 2 1
1 3 1
1 0

Example Output

1
0
#include <stdio.h>
#define INF 10000000

int main()
{
    int n, m, i, j, k, a, b, c;
    int map[101][101];
    while(scanf("%d %d", &n, &m) != EOF)
    {
        for(i = 1; i <= n; i++)      //map[i][j]代表从i点到j点的权值。先初始化
        {
            for(j = 1; j <= n; j++)
            {
                if(i == j)           //两点相等权值为0,否则就等于INF
                    map[i][j] = 0;
                else
                    map[i][j] = INF;
            }
        }
        while(m--)
        {
            scanf("%d %d %d", &a, &b, &c);
            if(map[a][b] > c)       //如果a到b的权值小于初始值,替代初始值
                map[a][b] = map[b][a] = c;
        }
        for(i = 1; i <= n; i++)     //找两个点之间的最小权值,用到i、j、k三个变量
        {
            for(j = 1; j <= n; j++)
            {
                for(k = 1; k <= n; k++)
                {
                    if(map[j][k] > map[j][i] + map[i][k])
                        map[j][k] = map[j][i] + map[i][k];
                }
            }
        }
        printf("%d\n", map[1][n]);
    }
    return 0;
}

转载自:https://blog.csdn.net/Fyn_Andersen/article/details/77542207

You may also like...

退出移动版