计蒜客：骑车比赛（Dijkstra）

 学习堆优化的写法

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m, a, b, c;
 4 typedef pair<int, int> pii; //first表示距离，second表示节点号
 5 vector<pii> graph[1005];
 6 set<pii> minHeap;
 7 vector<int> dis(1005, INT32_MAX);
 8 vector<bool> visited(1005, false); //记录已完成维护的点集
 9 void dij() {
10     while(!minHeap.empty()) { //维护最小堆以及dis、visited两个数组
11         auto iter = minHeap.begin();
12         int node = iter -> second;
13         minHeap.erase(*iter);
14         visited[node] = true;
15         for (auto i : graph[node]) {
16             if (!visited[i.second]) {
17                 if (dis[i.second] > dis[node] + i.first) {
18                     minHeap.erase(make_pair(dis[i.second], i.second));
19                     dis[i.second] = dis[node] + i.first;
20                     minHeap.insert(make_pair(dis[i.second], i.second));
21                 }
22             }
23         }
24     }
25 }
26 int main() {
27     cin >> n >> m;
28     while(m --) {
29         cin >> a >> b >> c;
30         graph[a].push_back(make_pair(c, b));
31         graph[b].push_back(make_pair(c, a));
32     }
33     dis[1] = 0;
34     minHeap.insert(make_pair(0, 1));
35     dij();
36     cout << dis[n] << endl;
37 }