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
|
#include <functional>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
long long N, M;
typedef pair<long long, long long> Edge;
// Performance improvement - Static array and different neighbour vectors for bigger and smaller
pair<vector<Edge>, vector<Edge>> graph[100005] = { { vector<Edge>(), vector<Edge>() } };
// Performance improvement? - Edge& rather than Edge
typedef pair<Edge&, bool> Qedge;
long long dijkstra(long long s) {
// Performance improvement - queue rather than priority_queue
queue<Qedge> q;
// Wrong answer on multiple tests - remove visited logic
// Performance improvement - from vector to statis array
// Wrong answer on a couple of tests - not init with { 0 }
long long distlt[100005] = { 0 };
long long distnlt[100005] = { 0 };
distlt[s] = distnlt[s] = 0;
Edge b = { 0, s };
q.push({b, true});
while (!q.empty()) {
auto c = q.front().first;
bool lt = q.front().second;
q.pop();
for (Edge& e : (lt) ? graph[c.second].second : graph[c.second].first) {
if (e.second == 0 || e.second == c.second) continue;
// cout << "From: " << c.second+1 << " To: " << e.second+1 << endl;
long long (&dist)[100005] = (lt) ? distlt : distnlt;
long long nd = ((!lt) ? distlt[c.second] : distnlt[c.second]) + e.first;
if (dist[e.second] == 0 || nd < dist[e.second]) {
dist[e.second] = nd;
q.push({ e, !lt });
}
// cout << dist[e.second] << endl;
}
}
if (distlt[N-1] == 0) return distnlt[N-1];
if (distnlt[N-1] == 0) return distlt[N-1];
return min(distlt[N-1], distnlt[N-1]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
for (long long i = 0; i < M; i++) {
long long ai, bi, di;
cin >> ai >> bi >> di;
ai--; bi--;
if (ai > bi) {
graph[ai].first.push_back({ di, bi });
graph[bi].second.push_back({ di, ai });
} else {
graph[ai].second.push_back({ di, bi });
graph[bi].first.push_back({ di, ai });
}
}
// long long shortest = 1000000005;
// dfs(0, 0, true, shortest);
// cout << shortest << endl;
cout << dijkstra(0) << endl;
}
|
