Submission #876469


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;
    }
    bool operator<(const Node &n)const{
        return cost > n.cost;
    }
};

int solve(){
    int N, M;
    scanf("%d %d", &N, &M);
    vector<vector<Node> > graph(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));
    }

    priority_queue<Node> que;
    que.push(Node(-1, 0, -1));
    vector<map<int, int> > memo(N, map<int, int>());
    while(!que.empty()){
        Node now = que.top();que.pop();
        if(memo[now.to].count(now.label) > 0)continue;
        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;
            next.cost = now.cost + (next.label == now.label ? 0 : 1);
            que.push(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 1672 Byte
Status
Exec Time 3198 ms
Memory 540500 KB

Compile Error

./Main.cpp: In function ‘int solve()’:
./Main.cpp:39: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 113 ms 11252 KB
03.txt 378 ms 28652 KB
04.txt 177 ms 17664 KB
05.txt 196 ms 19188 KB
06.txt 135 ms 20608 KB
07.txt 156 ms 18044 KB
08.txt 295 ms 24692 KB
09.txt 157 ms 17660 KB
10.txt 209 ms 21500 KB
11.txt 226 ms 32248 KB
12.txt 96 ms 9716 KB
13.txt 243 ms 26536 KB
14.txt 222 ms 32488 KB
15.txt 236 ms 23148 KB
16.txt 251 ms 26664 KB
17.txt 260 ms 33764 KB
18.txt 151 ms 18028 KB
19.txt 186 ms 24108 KB
20.txt 392 ms 49764 KB
21.txt 2507 ms 540500 KB
22.txt 1924 ms 278872 KB
23.txt 320 ms 35308 KB
24.txt 179 ms 21248 KB
25.txt 108 ms 12432 KB
26.txt 191 ms 19180 KB
27.txt 149 ms 16128 KB
28.txt 278 ms 26216 KB
29.txt 245 ms 25260 KB
30.txt 190 ms 20848 KB
31.txt 160 ms 18028 KB
32.txt 241 ms 24876 KB
33.txt 201 ms 24684 KB
34.txt 1676 ms 277992 KB
35.txt 111 ms 12416 KB
36.txt 502 ms 75680 KB
37.txt 217 ms 32236 KB
38.txt 1745 ms 278360 KB
sample_01.txt 4 ms 256 KB
sample_02.txt 4 ms 256 KB
sample_03.txt 4 ms 256 KB
w1.txt 223 ms 24896 KB
w10.txt 373 ms 15488 KB
w11.txt 540 ms 72608 KB
w12.txt 204 ms 24424 KB
w13.txt 3158 ms 15724 KB
w14.txt 731 ms 22272 KB
w15.txt 140 ms 15560 KB
w16.txt 159 ms 16364 KB
w17.txt 167 ms 17388 KB
w18.txt 308 ms 14720 KB
w2.txt 390 ms 28872 KB
w3.txt 358 ms 28396 KB
w4.txt 198 ms 19952 KB
w5.txt 277 ms 33384 KB
w6.txt 404 ms 49764 KB
w7.txt 3198 ms 531256 KB
w8.txt 3165 ms 139228 KB
w9.txt 3158 ms 14576 KB