Submission #2861002
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const int inf = 2e9; int n, m; vector<int> adj[N], col[N], imp[N]; vector<int> f[N]; int main() { ios_base::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v, c; cin >> u >> v >> c; col[u].push_back(c), col[v].push_back(c); imp[u].push_back(adj[v].size()), imp[v].push_back(adj[u].size()); adj[u].push_back(v), adj[v].push_back(u); } for (int i = 1; i <= n; ++i) { f[i].assign(adj[i].size(), (i == 1 ? 1 : inf)); } priority_queue<pair<int, pair<int,int> > , vector<pair<int, pair<int,int> > >, greater<pair<int, pair<int,int> > > > pq; for (int i = 0; i < adj[1].size(); ++i) pq.push({1, {1, i}}); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); int u = cur.second.first, id = cur.second.second; for (int i = 0; i < adj[u].size(); ++i) { int nu = adj[u][i], nid = imp[u][i]; int add = 1; if (col[u][id] == col[nu][nid]) add = 0; if (f[nu][nid] > f[u][id] + add) { f[nu][nid] = f[u][id] + add; pq.push({f[nu][nid], {nu, nid}}); } } } int res = inf; for (int i = 0;i < adj[n].size(); ++i) res = min(res, f[n][i]); if (res == inf) res = -1; cout << res << '\n'; }
Submission Info
Submission Time | |
---|---|
Task | E - Snuke's Subway Trip |
User | cazick |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1278 Byte |
Status | TLE |
Exec Time | 3157 ms |
Memory | 31600 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 600 | ||||
Status | AC |
|
Set Name | Test Cases |
---|---|
Sample | |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, sample_01.txt, sample_02.txt, sample_03.txt, w1.txt, w10.txt, w11.txt, w12.txt, w13.txt, w14.txt, w15.txt, w16.txt, w17.txt, w18.txt, w2.txt, w3.txt, w4.txt, w5.txt, w6.txt, w7.txt, w8.txt, w9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 5 ms | 9728 KB |
02.txt | TLE | 3156 ms | 24176 KB |
03.txt | AC | 299 ms | 25848 KB |
04.txt | AC | 138 ms | 24192 KB |
05.txt | AC | 319 ms | 27380 KB |
06.txt | AC | 83 ms | 22144 KB |
07.txt | AC | 131 ms | 22464 KB |
08.txt | AC | 324 ms | 25720 KB |
09.txt | AC | 135 ms | 22464 KB |
10.txt | AC | 137 ms | 22464 KB |
11.txt | TLE | 3156 ms | 25720 KB |
12.txt | TLE | 3156 ms | 18820 KB |
13.txt | TLE | 3156 ms | 23268 KB |
14.txt | TLE | 3156 ms | 31088 KB |
15.txt | TLE | 3156 ms | 25084 KB |
16.txt | TLE | 3156 ms | 24768 KB |
17.txt | TLE | 3156 ms | 25900 KB |
18.txt | TLE | 3156 ms | 18940 KB |
19.txt | TLE | 3157 ms | 27360 KB |
20.txt | TLE | 3157 ms | 31600 KB |
21.txt | TLE | 3156 ms | 24828 KB |
22.txt | TLE | 3156 ms | 25900 KB |
23.txt | AC | 540 ms | 28660 KB |
24.txt | TLE | 3156 ms | 24828 KB |
25.txt | TLE | 3156 ms | 18928 KB |
26.txt | TLE | 3156 ms | 19948 KB |
27.txt | TLE | 3156 ms | 30576 KB |
28.txt | TLE | 3156 ms | 24956 KB |
29.txt | TLE | 3156 ms | 24896 KB |
30.txt | TLE | 3156 ms | 25900 KB |
31.txt | TLE | 3156 ms | 19068 KB |
32.txt | TLE | 3157 ms | 27360 KB |
33.txt | TLE | 3156 ms | 26104 KB |
34.txt | TLE | 3156 ms | 27056 KB |
35.txt | TLE | 3156 ms | 20332 KB |
36.txt | TLE | 3156 ms | 21484 KB |
37.txt | TLE | 3157 ms | 27124 KB |
38.txt | TLE | 3156 ms | 25084 KB |
sample_01.txt | AC | 5 ms | 9600 KB |
sample_02.txt | AC | 4 ms | 9600 KB |
sample_03.txt | AC | 4 ms | 9600 KB |
w1.txt | TLE | 3157 ms | 27220 KB |
w10.txt | AC | 126 ms | 19328 KB |
w11.txt | TLE | 3156 ms | 20532 KB |
w12.txt | TLE | 3156 ms | 25084 KB |
w13.txt | AC | 452 ms | 17792 KB |
w14.txt | AC | 155 ms | 19328 KB |
w15.txt | TLE | 3156 ms | 21556 KB |
w16.txt | TLE | 3156 ms | 23800 KB |
w17.txt | AC | 659 ms | 24816 KB |
w18.txt | AC | 188 ms | 19328 KB |
w2.txt | TLE | 3157 ms | 27328 KB |
w3.txt | TLE | 3157 ms | 29408 KB |
w4.txt | TLE | 3157 ms | 26596 KB |
w5.txt | TLE | 3156 ms | 28768 KB |
w6.txt | TLE | 3157 ms | 26596 KB |
w7.txt | TLE | 3156 ms | 18364 KB |
w8.txt | TLE | 3156 ms | 17024 KB |
w9.txt | AC | 534 ms | 17664 KB |