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
AC × 51
WA × 8
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