-
Notifications
You must be signed in to change notification settings - Fork 1
/
MARYBMW - BMW.cc
64 lines (60 loc) · 1.44 KB
/
MARYBMW - BMW.cc
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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, LL> iLL;
typedef pair<LL, int> LLi;
typedef vector<iLL> viLL;
typedef vector<viLL> vviLL;
const LL INF = 1000000000000000001;
vviLL edges;
int N;
LL dist[50050];
LL Dijkstra() {
priority_queue<LLi, vector<LLi>> Q;
Q.push(LLi(INF, 1));
LLi curr;
LL speed;
dist[1] = INF;
for (int i = 2; i <= N; i++)
dist[i] = 0;
while (!Q.empty()) {
curr = Q.top();
Q.pop();
if (dist[curr.second] > curr.first)
continue;
if (curr.second == N)
return curr.first;
for (auto& e : edges[curr.second]) {
speed = min(e.second, curr.first);
if (speed > dist[e.first]) {
dist[e.first] = speed;
Q.push(LLi(speed, e.first));
}//if
}//for
}//while
return -1;
}//Dijkstra
template <typename T>
void fr(T& to) {
char t; to ^= to;
while (!isdigit((t = getchar_unlocked())));
while (t > 47) { to = (to << 3) + (to << 1) + t - 48; t = getchar_unlocked(); }
}//fr
int main() {
int T, E, n1, n2;
LL L, M, R, res, w, mx;
fr(T);
while (T--) {
fr(N); fr(E);
mx = 0;
edges.assign(N + 5, viLL());
while (E--) {
fr(n1); fr(n2); fr(w);
edges[n1].push_back(iLL(n2, w));
edges[n2].push_back(iLL(n1, w));
mx = max(mx, w);
}//while
printf("%lld\n", Dijkstra());
}//while
return 0;
}//main