-
Notifications
You must be signed in to change notification settings - Fork 13
/
Dijkstra.cpp
54 lines (51 loc) · 1.19 KB
/
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int arrival[N], departure[N], vis[N], parent[N];
vector<pair<int, int> > g[N];
void dijkstra(int source, int destination)
{
for(int i=1;i<=n;i++)
{
arrival[i]=1e18;
departure[i]=1e18;
vis[i]=0;
}
arrival[source]=0;
set<pair<int, int> > s;
s.insert({0, source});
while(!s.empty())
{
auto x = *(s.begin());
s.erase(x);
vis[x.second]=1;
departure[x.second]=arrival[x.second];
for(auto it:g[x.second])
{
if(arrival[it.first] > departure[x.second] + it.second)
{
s.erase({arrival[it.first], it.first});
arrival[it.first]=departure[x.second] + it.second;
s.insert({arrival[it.first], it.first});
parent[it.first]=x.second;
}
}
}
if(!vis[destination])
{
cout<<"-1";
return;
}
int v=destination;
vector<int> ans;
while(parent[v])
{
ans.push_back(v);
v=parent[v];
}
ans.push_back(source);
reverse(ans.begin(), ans.end());
for(auto it:ans)
cout<<it<<" ";
}
//Sample Problem 1 (Direct Dijkstra): https://codeforces.com/contest/20/problem/C
//Sample Solution 1: http://codeforces.com/contest/20/submission/39892416
//Sample Problem 2: http://codeforces.com/contest/230/problem/D
//Sample Solution 2: http://codeforces.com/contest/230/submission/39892295