Submission #877156


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 from, to, label, cost;
    Node(int f, int t, int l){
        from = f;
        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(p, q, c));
        graph[q].push_back(Node(q, p, c));
    }

    deque<Node> que;
    que.push_front(Node(-1, 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(memo[now.to].count(now.label) > 0)continue;
        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 (GCC 5.4.1)
Score 0
Code Size 1935 Byte
Status
Exec Time 3211 ms
Memory 635832 KB

Compile Error

./Main.cpp: In function ‘int solve()’:
./Main.cpp:38: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:43: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 124 ms 13696 KB
03.txt 262 ms 28800 KB
04.txt 192 ms 22784 KB
05.txt 217 ms 25984 KB
06.txt 123 ms 21760 KB
07.txt 127 ms 20864 KB
08.txt 220 ms 25472 KB
09.txt 130 ms 19968 KB
10.txt 144 ms 22400 KB
11.txt 203 ms 29048 KB
12.txt 101 ms 11252 KB
13.txt 142 ms 15348 KB
14.txt 163 ms 24704 KB
15.txt 192 ms 25336 KB
16.txt 235 ms 29052 KB
17.txt 237 ms 30708 KB
18.txt 124 ms 13688 KB
19.txt 169 ms 24688 KB
20.txt 189 ms 28032 KB
21.txt 152 ms 21112 KB
22.txt 1010 ms 173368 KB
23.txt 260 ms 34704 KB
24.txt 175 ms 24312 KB
25.txt 99 ms 10868 KB
26.txt 129 ms 12020 KB
27.txt 147 ms 20992 KB
28.txt 196 ms 27512 KB
29.txt 203 ms 27644 KB
30.txt 157 ms 21492 KB
31.txt 171 ms 23800 KB
32.txt 186 ms 26992 KB
33.txt 174 ms 23936 KB
34.txt 441 ms 92816 KB
35.txt 100 ms 10740 KB
36.txt 194 ms 27636 KB
37.txt 218 ms 41908 KB
38.txt 302 ms 62188 KB
sample_01.txt 4 ms 256 KB
sample_02.txt 4 ms 256 KB
sample_03.txt 4 ms 256 KB
w1.txt 178 ms 25168 KB
w10.txt 186 ms 14208 KB
w11.txt 118 ms 13052 KB
w12.txt 115 ms 13568 KB
w13.txt 877 ms 17012 KB
w14.txt 287 ms 19968 KB
w15.txt 117 ms 12244 KB
w16.txt 113 ms 12672 KB
w17.txt 129 ms 14336 KB
w18.txt 208 ms 15744 KB
w2.txt 249 ms 28240 KB
w3.txt 287 ms 29936 KB
w4.txt 198 ms 24304 KB
w5.txt 221 ms 28144 KB
w6.txt 201 ms 25328 KB
w7.txt 3211 ms 635832 KB
w8.txt 3158 ms 58840 KB
w9.txt 1121 ms 18424 KB