Submission #2379006
Source Code Expand
#include <bits/stdc++.h> #define rep(n) for(int i=0;i<n;i++) #define repp(j, n) for(int j=0;j<n;j++) #define reppp(i, m, n) for(int i=m;i<n;i++) #define all(c) c.begin(), c.end() #define rall(c) c.rbegin(), c.rend() #define debug(x) cerr << #x << ": " << x << endl; using namespace std; typedef long long ll; typedef pair<ll, ll> Pll; typedef pair<int, int> Pii; map<ll, ll> d; priority_queue< Pll, vector<Pll>, greater<Pll> > que; map<ll, vector<Pll> > edges; ll n,m,p,r,c; void dijkstra(ll start){ d[start] = 0LL; que.push(Pll(0LL, start)); while(!que.empty()){ Pll v = que.top(); que.pop(); if(d.find(v.second) != d.end() && d[v.second] < v.first) continue; for(Pll e: edges[v.second]){ if(d.find(e.first) == d.end() || d[e.first] > d[v.second] + e.second){ d[e.first] = d[v.second] + e.second; que.push(Pll(d[e.first], e.first)); } } } } int main() { std::ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; map<ll, ll> lines; ll next_line = 1; rep(m){ cin >> p >> r >> c; p--; r--; if(lines[c] == 0) lines[c] = next_line++; c = lines[c]; edges[p*(m+1LL)+c].emplace_back(r*(m+1LL)+c, 0LL); edges[r*(m+1LL)+c].emplace_back(p*(m+1LL)+c, 0LL); edges[p*(m+1LL)].emplace_back(p*(m+1LL)+c, 0LL); edges[p*(m+1LL)+c].emplace_back(p*(m+1LL), 1LL); edges[r*(m+1LL)].emplace_back(r*(m+1LL)+c, 0LL); edges[r*(m+1LL)+c].emplace_back(r*(m+1LL), 1LL); } dijkstra(0LL); if(d.find((n-1LL)*(m+1LL)) == d.end()){ cout << -1 << endl; }else{ cout << d[(n-1LL)*(m+1LL)] << endl; } }
Submission Info
Submission Time | |
---|---|
Task | E - Snuke's Subway Trip |
User | Noimin |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1776 Byte |
Status | AC |
Exec Time | 1718 ms |
Memory | 111604 KB |
Judge Result
Set Name | Sample | All | ||
---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 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 | 2 ms | 384 KB |
02.txt | AC | 847 ms | 43384 KB |
03.txt | AC | 1718 ms | 111604 KB |
04.txt | AC | 610 ms | 68096 KB |
05.txt | AC | 1340 ms | 81648 KB |
06.txt | AC | 625 ms | 54272 KB |
07.txt | AC | 730 ms | 56188 KB |
08.txt | AC | 1689 ms | 110968 KB |
09.txt | AC | 786 ms | 61436 KB |
10.txt | AC | 791 ms | 61308 KB |
11.txt | AC | 739 ms | 61412 KB |
12.txt | AC | 155 ms | 24412 KB |
13.txt | AC | 504 ms | 38112 KB |
14.txt | AC | 764 ms | 60500 KB |
15.txt | AC | 612 ms | 50032 KB |
16.txt | AC | 695 ms | 55656 KB |
17.txt | AC | 840 ms | 63468 KB |
18.txt | AC | 336 ms | 29160 KB |
19.txt | AC | 664 ms | 55504 KB |
20.txt | AC | 864 ms | 66284 KB |
21.txt | AC | 1552 ms | 100716 KB |
22.txt | AC | 966 ms | 70000 KB |
23.txt | AC | 1118 ms | 78316 KB |
24.txt | AC | 803 ms | 63852 KB |
25.txt | AC | 155 ms | 23408 KB |
26.txt | AC | 472 ms | 37360 KB |
27.txt | AC | 846 ms | 68204 KB |
28.txt | AC | 800 ms | 64620 KB |
29.txt | AC | 806 ms | 66156 KB |
30.txt | AC | 763 ms | 63344 KB |
31.txt | AC | 490 ms | 38128 KB |
32.txt | AC | 685 ms | 56044 KB |
33.txt | AC | 824 ms | 67180 KB |
34.txt | AC | 611 ms | 50928 KB |
35.txt | AC | 136 ms | 24176 KB |
36.txt | AC | 321 ms | 30708 KB |
37.txt | AC | 718 ms | 53748 KB |
38.txt | AC | 614 ms | 51312 KB |
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
w1.txt | AC | 764 ms | 55544 KB |
w10.txt | AC | 960 ms | 79360 KB |
w11.txt | AC | 209 ms | 23816 KB |
w12.txt | AC | 392 ms | 30336 KB |
w13.txt | AC | 776 ms | 50816 KB |
w14.txt | AC | 914 ms | 74112 KB |
w15.txt | AC | 104 ms | 23768 KB |
w16.txt | AC | 175 ms | 24960 KB |
w17.txt | AC | 287 ms | 28160 KB |
w18.txt | AC | 642 ms | 41984 KB |
w2.txt | AC | 695 ms | 55416 KB |
w3.txt | AC | 953 ms | 69312 KB |
w4.txt | AC | 778 ms | 56812 KB |
w5.txt | AC | 1591 ms | 111216 KB |
w6.txt | AC | 1115 ms | 82032 KB |
w7.txt | AC | 1211 ms | 92792 KB |
w8.txt | AC | 1276 ms | 95232 KB |
w9.txt | AC | 1395 ms | 95104 KB |