Submission #878010


Source Code Expand

Copy
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

#define REP(i,x) for(int i=0 ; i<(int)(x) ; i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

struct Node{
    int to, label, cost;
    Node(int t, int l){
        to = t;
        label = l;
        cost = 0;
    }
};

const int MAX = 1<<30;

int solve(){
    int N, M;
    scanf("%d %d", &N, &M);
    vector<vector<Node> > graph(N);
    vector<set<int> > have(N);
    REP(i, M){
        int p, q, c;
        scanf("%d %d %d", &p, &q, &c);
        p--;
        q--;
        graph[p].push_back(Node(q, c));
        graph[q].push_back(Node(p, c));
    }

    stack<int> st;
    vector<int> used(N);
    st.push(0);
    bool ok = false;
    while(!st.empty()){
        int v = st.top();st.pop();
        if(v==N-1){
            ok = true;
            break;
        }
        used[v] = 1;
        REP(i, graph[v].size()){
            int to = graph[v][i].to;
            if(used[to])continue;
            st.push(to);
        }
    }
    if(!ok)return -1;

    deque<Node> que;
    que.push_front(Node(0, -1));
    vector<map<int, int> > memo(N, map<int, int>());
    vector<int> memo2(N, MAX);
    while(!que.empty()){
        Node now = que.front();que.pop_front();
        if(now.to==N-1)return now.cost;
        if(memo2[now.to] == MAX)memo2[now.to] = now.cost;
        memo[now.to][now.label] = now.cost;
        REP(i, graph[now.to].size()){
            Node next = graph[now.to][i];
            if(memo2[next.to] < now.cost)continue;
            if(memo[next.to].count(next.label) > 0)continue;
            if(next.label == now.label){
                next.cost = now.cost;
                que.push_front(next);
            }else{
                next.cost = now.cost + 1;
                que.push_back(next);
            }
        }
    }
    return -1;
}

int main(){
    int res = solve();
    printf("%d\n", res);
    return 0;
}

Submission Info

Submission Time
Task E - Snuke's Subway Trip
User nel215
Language C++14 (Clang 3.8.0)
Score 0
Code Size 2257 Byte
Status
Exec Time 3241 ms
Memory 971376 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 0 / 600 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, 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 11 ms 888 KB
02.txt 116 ms 11008 KB
03.txt 239 ms 22272 KB
04.txt 160 ms 13440 KB
05.txt 197 ms 19584 KB
06.txt 115 ms 15872 KB
07.txt 126 ms 15488 KB
08.txt 199 ms 19072 KB
09.txt 113 ms 14464 KB
10.txt 138 ms 16896 KB
11.txt 199 ms 22588 KB
12.txt 101 ms 9400 KB
13.txt 149 ms 14136 KB
14.txt 151 ms 18432 KB
15.txt 139 ms 12604 KB
16.txt 225 ms 23664 KB
17.txt 204 ms 24504 KB
18.txt 123 ms 11196 KB
19.txt 152 ms 18484 KB
20.txt 176 ms 21268 KB
21.txt 151 ms 15292 KB
22.txt 907 ms 126392 KB
23.txt 268 ms 27392 KB
24.txt 153 ms 18364 KB
25.txt 101 ms 9912 KB
26.txt 120 ms 9912 KB
27.txt 143 ms 15220 KB
28.txt 180 ms 21308 KB
29.txt 188 ms 21268 KB
30.txt 137 ms 15800 KB
31.txt 243 ms 31292 KB
32.txt 193 ms 23476 KB
33.txt 171 ms 17776 KB
34.txt 539 ms 98620 KB
35.txt 99 ms 9016 KB
36.txt 462 ms 73784 KB
37.txt 240 ms 39424 KB
38.txt 343 ms 61244 KB
sample_01.txt 4 ms 256 KB
sample_02.txt 4 ms 256 KB
sample_03.txt 4 ms 256 KB
w1.txt 167 ms 18980 KB
w10.txt 156 ms 9344 KB
w11.txt 118 ms 10736 KB
w12.txt 121 ms 11008 KB
w13.txt 3154 ms 11324 KB
w14.txt 151 ms 9600 KB
w15.txt 111 ms 10136 KB
w16.txt 115 ms 10368 KB
w17.txt 131 ms 11776 KB
w18.txt 377 ms 13440 KB
w2.txt 3168 ms 22300 KB
w3.txt 3159 ms 24116 KB
w4.txt 175 ms 18100 KB
w5.txt 191 ms 20788 KB
w6.txt 193 ms 19764 KB
w7.txt 3195 ms 462544 KB
w8.txt 3216 ms 700916 KB
w9.txt 3241 ms 971376 KB