Submission #878419


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>());
    while(!que.empty()){
        Node now = que.front();que.pop_front();
        if(now.to==N-1)return now.cost;
        memo[now.to][now.label] = now.cost;
        REP(i, graph[now.to].size()){
            Node next = graph[now.to][i];
            if(memo[next.to].count(next.label) > 0)continue;
            if(next.label == now.label){
                next.cost = now.cost;
                que.push_front(next);
            }else if(now.label == -1){
                next.cost = now.cost + 1;
                que.push_back(next);
            }else{
                next.cost = now.cost;
                next.to = now.to;
                next.label = -1;
                que.push_front(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 (GCC 5.4.1)
Score 0
Code Size 2301 Byte
Status
Exec Time 3301 ms
Memory 1189752 KB

Compile Error

./Main.cpp: In function ‘int solve()’:
./Main.cpp:37:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
                           ^
./Main.cpp:42:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &p, &q, &c);
                                      ^

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 4 ms 256 KB
02.txt 3213 ms 948452 KB
03.txt 3230 ms 803560 KB
04.txt 166 ms 15872 KB
05.txt 394 ms 48952 KB
06.txt 179 ms 28288 KB
07.txt 237 ms 25728 KB
08.txt 3225 ms 747656 KB
09.txt 3189 ms 345736 KB
10.txt 3191 ms 373636 KB
11.txt 3255 ms 1042492 KB
12.txt 3243 ms 907972 KB
13.txt 3266 ms 1133824 KB
14.txt 3301 ms 703544 KB
15.txt 148 ms 14908 KB
16.txt 3229 ms 732508 KB
17.txt 3261 ms 1068520 KB
18.txt 1746 ms 460540 KB
19.txt 3261 ms 1081784 KB
20.txt 3255 ms 1016684 KB
21.txt 3262 ms 1099708 KB
22.txt 3263 ms 1098132 KB
23.txt 3267 ms 1147296 KB
24.txt 3255 ms 1010876 KB
25.txt 1584 ms 520688 KB
26.txt 175 ms 23352 KB
27.txt 337 ms 68384 KB
28.txt 3263 ms 1097148 KB
29.txt 3256 ms 1024028 KB
30.txt 3240 ms 853744 KB
31.txt 3268 ms 1157300 KB
32.txt 3237 ms 812188 KB
33.txt 3257 ms 1036988 KB
34.txt 3262 ms 1092488 KB
35.txt 103 ms 9528 KB
36.txt 3272 ms 1189752 KB
37.txt 3267 ms 1135452 KB
38.txt 3264 ms 1104776 KB
sample_01.txt 4 ms 256 KB
sample_02.txt 4 ms 256 KB
sample_03.txt 4 ms 256 KB
w1.txt 3264 ms 1109120 KB
w10.txt 151 ms 9856 KB
w11.txt 3244 ms 886828 KB
w12.txt 3248 ms 928184 KB
w13.txt 3199 ms 389404 KB
w14.txt 152 ms 10112 KB
w15.txt 3230 ms 733812 KB
w16.txt 231 ms 36244 KB
w17.txt 233 ms 38420 KB
w18.txt 3159 ms 16852 KB
w2.txt 3264 ms 1096616 KB
w3.txt 3262 ms 1080768 KB
w4.txt 189 ms 22452 KB
w5.txt 3263 ms 1096768 KB
w6.txt 3263 ms 1091264 KB
w7.txt 3253 ms 981720 KB
w8.txt 3240 ms 849004 KB
w9.txt 3221 ms 641388 KB