my-view-dijkstra

发表于

最近经常用到单源最短路径，遂来整理一波

dijkstra算法是典型的用来解决单源最短路径的算法
我们可以通过三个数组很好的解决他。

  • map数组，二维的，用来记录每个点到其他点的权值。
  • dis数组，一维的，用来记录起点到其他点的最小值。
  • flag数组，一维的，用来记录哪个顶点不再需要更新。

废话少说，附上代码
题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
using namespace std;
int road[1005][1005];
int flag[1005];
int dis[1005];
int pos[105];
int t;
int n,m,p,q;
int ans;
int dijs(){
   for (int i = 0; i < m; ++i) {
       dis[i] = road[q][i];
   }
   for (int i = 0; i < m; ++i) {
       // 先找到最小的一个作为更新点
       int pivot = INF, u = -1;
       for (int j = 0; j < m; ++j) {
           if (pivot>dis[j]&&!flag[j]){
               pivot = dis[j];
               u = j;
           }
       }
       flag[u] = 1;
       // u为更新点
       for (int j = 0; j < m; ++j) {
           if (!flag[j]){
               dis[j] = min(dis[j], dis[u]+road[u][j]);
           }
       }
   }
   ans = INF;
   for (int k = 0; k < n; ++k) {
       ans = min(dis[pos[k]],ans);
   }
   return ans;
}
int main(){
   cin>>t;
   while (t--){
       memset(road, INF,sizeof(road));
       memset(flag,0,sizeof(flag));
       cin>>n>>m>>p>>q;
       for (int i = 0; i <n; ++i) {
           cin>>pos[i];
       }
       int x,y,val;
       for (int i = 0; i < p; ++i) {
           cin>>x>>y>>val;
           road[x][y] = road[y][x] = min(road[x][y], val);
       }
       ans = dijs();  // 从q开始出发,到达士兵的时间
       cout<<ans<<endl;
   }
}