朴素及堆优化的Dijkstra算法

先放个板子（我自己写的）之后有时间了再写思路；

朴素的dijkstra：

题目链接：https://www.luogu.com.cn/problem/P3371

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include<string>
 6 #include
 7 #include
 8 #include
 9 #define inf 0x3f3f3f3f
10 using namespace std;
11 const int N = 10000 + 10;
12 
13 int dis[N], vis[N];
14 int n, m, s;
15 
16 struct node {
17     int to, val;
18 };
19 vectorG[N];
20 
21 void dijkstra(int t) {
22 
23     /*for (int i = 1; i <= n; i++) {
24         dis[i] = G[t][i];
25     }*/
26     //vis[t] = 1;
27     memset(dis,0x3f,sizeof(dis));
28     memset(vis,0,sizeof(vis));
29     dis[t] = 0;
30     for (int i = 1; i <= n; i++) {
31         int k = 0, rem = inf;
32         for (int j = 1; j <= n; j++) {
33             if (!vis[j] && dis[j] < rem) {
34                 k = j;
35                 rem = dis[j];
36             }
37         }
38         vis[k] = 1;
39         if (rem == inf) break;
40         for (int j = 0; j < G[k].size(); j++) {
41             int fto = G[k][j].to, val = G[k][j].val;
42             if (!vis[fto] && dis[k] + val < dis[fto]) {
43                 dis[fto] = dis[k] + val;
44             }
45         }
46     }
47 
48     return;
49 }
50 
51 int main() {
52 
53     //int  n, m;
54     cin >> n >> m >> s;
55     //memset(G, 0x3f, sizeof(G));
56     memset(dis, 0x3f, sizeof(dis));
57     for (int i = 1; i <= m; i++) {
58         int u, v, d;
59         cin >> u >> v >> d;
60 //        if (u == s) {
61 //            dis[v] = min(dis[v], d);
62 //        }
63         //G[u][v] = min(G[u][v], d);
64         //G[v][u] = d;
65         node f;
66         f.to = v;
67         f.val = d;
68         G[u].push_back(f);
69     }
70     dijkstra(s);
71     for (int i = 1; i <= n; i++) {
72         if (dis[i] == 0x3f3f3f3f) cout << 2147483647 << " ";
73         else cout << dis[i] << " ";
74     }
75 
76     return 0;
77 }

堆优化的dijkstra：

题目链接：https://www.luogu.com.cn/problem/P4779

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include<string>
 6 #include
 7 #include
 8 #include
 9 #define inf 0x3f3f3f3f
10 using namespace std;
11 const int N = 100000 + 10;
12 
13 int dis[N], vis[N];
14 int n, m, s;
15 
16 struct point{
17     int dis;
18     int pos;
19     bool operator <(const point& x)const
20     {
21         return x.dis < dis;
22     }
23 };
24 priority_queuepq;
25 
26 struct node {
27     int to, val;
28 };
29 vectorG[N];
30 
31 void dijkstra(int t) {
32 
33     dis[t] = 0;
34     point h;
35     h.dis = 0, h.pos = t;
36     pq.push(h);
37     while (!pq.empty()) {
38         point tmp = pq.top();
39         pq.pop();
40         int p = tmp.pos, d = tmp.dis;
41         if (vis[p]) continue;
42         vis[p] = 1;
43         for (int i = 0; i < G[p].size(); i++) {
44             int frt = G[p][i].to, dist = G[p][i].val;
45             if (!vis[frt] && dis[p] + dist < dis[frt]) {
46                 dis[frt] = dis[p] + dist;
47                 point hh;
48                 hh.dis = dis[frt], hh.pos = frt;
49                 pq.push(hh);
50             }
51         }
52     }
53     return;
54 }
55 
56 int main() {
57 
58     //int  n, m;
59     cin >> n >> m >> s;
60     //memset(G, 0x3f, sizeof(G));
61     memset(dis, 0x3f, sizeof(dis));
62     for (int i = 1; i <= m; i++) {
63         int u, v, d;
64         cin >> u >> v >> d;
65         /*if (u == s) {
66             dis[v] = min(dis[v], d);
67         }*/
68         //G[u][v] = min(G[u][v], d);
69         //G[v][u] = d;
70         node f;
71         f.to = v;
72         f.val = d;
73         G[u].push_back(f);
74     }
75     dijkstra(s);
76     for (int i = 1; i <= n; i++) {
77         cout << dis[i] << " ";
78     }
79 
80     return 0;
81 }
最短路算法

相关

标签