【计蒜客】骑车比赛 堆优化 + Dijkstra

题目链接骑车比赛

[kuangbin带你飞]专题六最短路

题目描述

在这里插入图片描述


思路

Dijkstra算法:
裸的最短路问题,求顶点1到顶点n的最短路;用堆优化的Dijkstar可以过;
本题用前向星存了下图,用优先队列模拟实现小根堆;

代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

//Hang_cccccc
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 1010
#define MAX_M 10010
#define INF 0x3f3f3f3f

int dist[MAX_N], vis[MAX_N], head[MAX_N], cnt = 0;

struct Node{
int to, val, next;
}edge[MAX_M];

struct Min_Heap{
int key, val;
Min_Heap(int tmp_key, int tmp_val)
{
key = tmp_key;
val = tmp_val;
}
bool operator < (const Min_Heap &a) const
{
return a.val < val;
}
};

void init(int n)
{
memset(vis, 0, sizeof(vis));
memset(head, -1, sizeof(head));
for(int i = 1; i<=n; i++)
dist[i] = INF;
}

void add(int x, int y, int val)
{
edge[cnt].to = y;
edge[cnt].val =val;
edge[cnt].next = head[x];
head[x] = cnt++;
}

void Dijkstra(int n, int v)
{
dist[v] = 0;
priority_queue<Min_Heap> S;
S.push(Min_Heap(v, 0));
while(!S.empty())
{
Min_Heap h = S.top();
S.pop();
if(vis[h.key])
continue;
vis[h.key] = 1;
for(int j = head[h.key]; j != -1; j = edge[j].next)
{
int k = edge[j].to;
if(!vis[k])
{
dist[k] = min(dist[k], h.val + edge[j].val);
S.push(Min_Heap(k, dist[k]));
}
}
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
init(n);
for(int i = 1; i<=m; i++)
{
int x, y, val;
cin >> x >> y >> val;
add(x, y, val);
add(y, x, val);
}
Dijkstra(n, 1);
cout << dist[n];
return 0;
}
-------------本文结束,感谢您的阅读!-------------