Submission #2377914
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; 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); ll n,m,p,r,c; cin >> n >> m; rep(m){ cin >> p >> r >> c; p--; r--; 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); 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 | 0 |
Code Size | 1560 Byte |
Status | WA |
Exec Time | 1787 ms |
Memory | 100340 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 | 2 ms | 384 KB |
02.txt | AC | 952 ms | 43384 KB |
03.txt | AC | 1713 ms | 100340 KB |
04.txt | WA | 644 ms | 68096 KB |
05.txt | AC | 1465 ms | 81648 KB |
06.txt | AC | 661 ms | 54272 KB |
07.txt | AC | 829 ms | 56188 KB |
08.txt | AC | 1787 ms | 99572 KB |
09.txt | AC | 940 ms | 61436 KB |
10.txt | AC | 849 ms | 61308 KB |
11.txt | AC | 857 ms | 61284 KB |
12.txt | AC | 164 ms | 24796 KB |
13.txt | AC | 551 ms | 38112 KB |
14.txt | AC | 770 ms | 61072 KB |
15.txt | WA | 682 ms | 50032 KB |
16.txt | AC | 721 ms | 55784 KB |
17.txt | AC | 824 ms | 62956 KB |
18.txt | AC | 348 ms | 29160 KB |
19.txt | AC | 696 ms | 55504 KB |
20.txt | AC | 916 ms | 65644 KB |
21.txt | AC | 1451 ms | 96236 KB |
22.txt | AC | 1010 ms | 69360 KB |
23.txt | AC | 1170 ms | 79468 KB |
24.txt | AC | 900 ms | 64876 KB |
25.txt | AC | 162 ms | 23536 KB |
26.txt | AC | 507 ms | 37360 KB |
27.txt | AC | 940 ms | 67564 KB |
28.txt | AC | 820 ms | 65900 KB |
29.txt | AC | 831 ms | 66156 KB |
30.txt | AC | 783 ms | 64240 KB |
31.txt | AC | 503 ms | 38128 KB |
32.txt | AC | 800 ms | 55532 KB |
33.txt | AC | 912 ms | 67180 KB |
34.txt | AC | 630 ms | 50800 KB |
35.txt | AC | 142 ms | 24176 KB |
36.txt | AC | 342 ms | 30708 KB |
37.txt | AC | 712 ms | 53748 KB |
38.txt | AC | 655 ms | 51184 KB |
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | WA | 1 ms | 256 KB |
w1.txt | AC | 782 ms | 55416 KB |
w10.txt | WA | 1438 ms | 87936 KB |
w11.txt | AC | 206 ms | 23556 KB |
w12.txt | AC | 400 ms | 30336 KB |
w13.txt | AC | 818 ms | 50816 KB |
w14.txt | WA | 910 ms | 74112 KB |
w15.txt | AC | 104 ms | 23640 KB |
w16.txt | AC | 175 ms | 24960 KB |
w17.txt | AC | 301 ms | 28032 KB |
w18.txt | AC | 751 ms | 41984 KB |
w2.txt | AC | 775 ms | 55416 KB |
w3.txt | AC | 1028 ms | 69312 KB |
w4.txt | AC | 880 ms | 56556 KB |
w5.txt | AC | 1690 ms | 99824 KB |
w6.txt | AC | 1191 ms | 82032 KB |
w7.txt | WA | 1390 ms | 81912 KB |
w8.txt | WA | 1347 ms | 82928 KB |
w9.txt | WA | 1364 ms | 83840 KB |