-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstra.cpp
37 lines (35 loc) · 972 Bytes
/
dijkstra.cpp
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
/* dijkstra */
const int MAXN = 1e5+5;
vector<pair<int, int> > adj[MAXN]; //{dist, adjacent_vertex}
ll dist[MAXN];
bool vis[MAXN];
int n;
void init(){
for(int i = 1;i <= n; i++){
adj[i].clear();
dist[i] = (int)1e6;
vis[i] = false;
}
}
void dijkstra(int st, int finish){
dist[st] = 0;
multiset<pair<int, int> > S;
S.insert({0,st});
while(!S.empty()){
auto p = *(S.begin());
S.erase(S.begin());
int u = p.second;
if(vis[u]) // distance to the visited vertices is minimal.
continue;
vis[u] = true;
int v, wuv;
for(auto p : adj[u]){
v = p.second;
wuv = p.first;
if(dist[u] + wuv < dist[v]){
dist[v] = dist[u] + wuv;
S.insert({dist[v], v}); //a vertex can be pushed multiple times do not mark vis as true while pushing instead mark it while popping out.
}
}
}
}