最短路

1.稠密图用邻接矩阵来存

朴素版dijkstra 算法

acwing 849

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 510;
 5 int n,m;
 6 int dis[N]; //每个点到起点的最短距离(路)
 7 int g[N][N]; //稠密图邻接矩阵来存
 8 bool st[N]; //该集合表示状态，表示最短距离已经被确定的点
 9 
10 int dijkstra()
11 {
12     memset(dis,0x3f, sizeof dis); //初始化后面每一个点到起点的距离为无穷
13     dis[1] = 0; //第一个点到起点的距离为0
14     
15     for (int i = 0; i < n; i ++ )
16     {
17         int t  = -1; //不在st集合中距离起点最近的点
18         for (int j = 1; j <= n; j ++ ) //枚举每一个点
19             if(!st[j] && (t == -1 || dis[j] < dis[t])) ///该步骤即寻找还未确定最短路的点中路径最短的点
20             t = j; //更新最短距离 ,是t表示距离起点最近
21             
22             st[t] = true; //标记
23         
24         for (int j = 1; j <= n; j ++ ) //依次更新每个点到相邻点的路径值
25            dis[j] = min(dis[j],dis[t] + g[t][j]);  //t这个点到起点的最短距离 + t到j 的距离
26     }
27     
28     if(dis[n] == 0x3f3f3f3f) return -1; //起点和N不连通
29     return dis[n];
30 }
31 
32 
33 
34 int main()
35 { //自环不是最小的，会越来越大，可以不用判断
36     scanf("%d%d", &n, &m);
37     
38     memset(g,0x3f, sizeof g);
39     
40     while (m -- )
41     {
42         int a,b,c;
43         scanf("%d%d%d", &a, &b, &c);
44         g[a][b] = min(g[a][b],c); //如果有重边，取最短的边
45         
46     }
47 
48     int t = dijkstra();
49     
50     printf("%d\n",t);
51     return 0;
52 }