#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
const int inf = 9999999;
int minn,flag;
int main(void)
{
int a[105][105];
int dij[105];
int vis[105];
int n , m;
scanf("%d %d",&n, &m);
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= n ; j ++)
{
if(i == j)
a[i][j] = 0;
else
a[i][j] = inf;
}
}//初始化图
int from , to ,val;
for(int i = 1 ; i <= m ; i ++)
{
scanf("%d %d %d",&from,&to,&val);
a[from][to] = val;
}//输入边权
for(int i = 1 ; i <= n ; i++)
dij[i] = a[1][i];//一号点到所有点的距离
memset(vis,0,sizeof(vis));
vis[1] = 1;
//dij算法核心
for(int i = 1 ; i <= n - 1 ; i ++)
{
minn = inf;
for(int j = 1 ; j <= n ; j ++)//寻找距离一号点最近的那个点
{
if(vis[j] == 0 && dij[j] < minn)
{
minn = dij[j];
flag = j;
}
}
vis[flag] = 1;
for(int k = 1 ; k <= n ; k ++)//寻找对应点出边，并进行"松弛"处理
{
if(a[flag][k] < inf)
{
if(dij[k] > dij[flag] + a[flag][k])
dij[k] = dij[flag] + a[flag][k];
}
}
}
for(int i = 1 ; i <= n ; i ++)
printf("%d ",dij[i]);
return 0;
}
测试数据：
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
输出数据：
0 1 8 4 13 17
