Submission #2860956
Source Code Expand
#include <bits/stdc++.h> using namespace std; struct State { int dist; int u; int c; }; const int N = 100005, M = 200005; int n, m; vector< pair<int,int> > G[N]; map <int,int> d[N]; void dijkstra() { deque<State> q; q.push_back({0, 1, 0}); d[1][0] = 0; while(!q.empty()) { State f = q.front(); q.pop_front(); int u = f.u, c = f.c; if (f.dist != d[u][c]) continue; if (!d[u].count(0) || (d[u].count(0) && d[u][0] > f.dist)) { d[u][0] = f.dist; //q.push_front({f.dist, u, 0}); } if (c) { int pos = lower_bound(G[u].begin(), G[u].end(), make_pair(c, 0)) - G[u].begin(); while(pos < G[u].size() && G[u][pos].first == c) { int v = G[u][pos].second; if (!d[v].count(c) || (d[v].count(c) && d[v][c] > f.dist)) { d[v][c] = f.dist; q.push_front({f.dist, v, c}); } ++pos; } } else { for (auto e : G[u]) { int v = e.second, cc = e.first; if (!d[v].count(cc) || (d[v].count(cc) && d[v][cc] > f.dist + 1)) { d[v][cc] = f.dist + 1; q.push_back({f.dist + 1, v, cc}); } } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; while(m--) { int u, v, c; cin >> u >> v >> c; G[u].push_back(make_pair(c, v)); G[v].push_back(make_pair(c, u)); } for (int i = 1; i <= n; ++i) { sort(G[i].begin(), G[i].end()); } dijkstra(); if (!d[n].count(0)) cout << -1 << endl; else cout << d[n][0] << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - Many Formulas |
User | vivukhue |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1467 Byte |
Status | RE |
Exec Time | 101 ms |
Memory | 7296 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 300 | ||||
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, sample_01.txt, sample_02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | RE | 100 ms | 7296 KB |
02.txt | RE | 101 ms | 7296 KB |
03.txt | RE | 101 ms | 7296 KB |
04.txt | WA | 4 ms | 7296 KB |
05.txt | RE | 99 ms | 7296 KB |
06.txt | RE | 100 ms | 7296 KB |
07.txt | RE | 100 ms | 7296 KB |
08.txt | RE | 100 ms | 7296 KB |
09.txt | WA | 4 ms | 7296 KB |
10.txt | WA | 4 ms | 7296 KB |
sample_01.txt | WA | 4 ms | 7296 KB |
sample_02.txt | RE | 99 ms | 7296 KB |