-
Notifications
You must be signed in to change notification settings - Fork 0
/
RadixHeap-64bit.test.cpp
73 lines (64 loc) · 1.46 KB
/
RadixHeap-64bit.test.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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#define PROBLEM "https://yukicoder.me/problems/no/807"
#include <vector>
#include <iostream>
#include <array>
#include <algorithm>
using namespace std;
#include "../../lib/00-util/FastIO.cpp"
#include "../../lib/15-queue/RadixHeap.cpp"
//Dijkstra
template<class T> class Dijkstra {
public:
int N;
T inf;
vector<T> cost;
vector<vector<pair<T, int>>> edge;
Dijkstra(const int N, T inf) : N(N), inf(inf), cost(N), edge(N) {
}
void make_edge(int from, int to, T w) {
edge[from].push_back({ w,to });
}
void solve(int start) {
for (int i = 0; i < N; ++i) cost[i] = inf;
RadixHeap<int,unsigned long long> pq(0);
cost[start] = 0;
pq.push({ 0,start });
while (!pq.empty()) {
auto p = pq.pop();
T v = p.first;
int from = p.second;
if(cost[from]<v) continue;
for (auto u : edge[from]) {
T w = v + u.first;
int to = u.second;
if (w < cost[to]) {
cost[to] = w;
pq.push({ w,to });
}
}
}
return;
}
};
int main() {
cin.tie(0);ios::sync_with_stdio(false);
int N, M;
read(N); read(M);
Dijkstra<long long> dijk(2*N, 1LL<<60);
for(int i = 0; i < M; ++i){
int a, b;
long long c;
read(a); read(b); read(c);
a--, b--;
dijk.make_edge(a, b, c);
dijk.make_edge(b, a, c);
dijk.make_edge(a+N, b+N, c);
dijk.make_edge(b+N, a+N, c);
dijk.make_edge(a, b+N, 0);
dijk.make_edge(b, a+N, 0);
}
dijk.solve(0);
dijk.cost[N]=0;
for (int i = 0; i < N; ++i) cout << dijk.cost[i]+dijk.cost[i+N] << "\n";
return 0;
}