# 单源最短路(dijkstra)模板

xiaoxiao2021-03-01  10

#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