图结构练习——最短路径
目录
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
