Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #878638

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, cost;
Node(int t, int c){
to = t;
cost = c;
}
};

const int MAX = 1<<30;

struct Input{
int p, q, c;
};

void set_node(pair<int, int> p, map<pair<int,int>, int> &node_number){
if(node_number.count(p))return;
int s = node_number.size();
node_number[p] = s;
};

int solve(){
int N, M;
scanf("%d %d", &N, &M);
vector<Input> inputs;
map<pair<int,int>, int> node_number;
node_number[make_pair(0, -1)] = 0;
node_number[make_pair(N-1, -1)] = 1;
REP(i, M){
Input inp;
scanf("%d %d %d", &inp.p, &inp.q, &inp.c);
inp.p--;
inp.q--;
pair<int, int> p0 = make_pair(inp.p, -1);
pair<int, int> p1 = make_pair(inp.q, -1);
pair<int, int> p2 = make_pair(inp.p, inp.c);
pair<int, int> p3 = make_pair(inp.q, inp.c);
set_node(p0, node_number);
set_node(p1, node_number);
set_node(p2, node_number);
set_node(p3, node_number);
inputs.push_back(inp);
}

vector<vector<Node> > graph(node_number.size());
REP(i, inputs.size()){
Input inp = inputs[i];

int p0 = node_number[make_pair(inp.p, -1)];
int p1 = node_number[make_pair(inp.q, -1)];
int p2 = node_number[make_pair(inp.p, inp.c)];
int p3 = node_number[make_pair(inp.q, inp.c)];

graph[p0].push_back(Node(p2, 1));
graph[p2].push_back(Node(p0, 0));
graph[p1].push_back(Node(p3, 1));
graph[p3].push_back(Node(p1, 0));
graph[p2].push_back(Node(p3, 0));
graph[p3].push_back(Node(p2, 0));
}

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

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

#### Submission Info

Submission Time 2016-09-11 23:41:48+0900 E - Snuke's Subway Trip nel215 C++14 (GCC 5.4.1) 600 2822 Byte AC 1596 ms 66736 KB

#### Compile Error

./Main.cpp: In function ‘int solve()’:
./Main.cpp:46: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:53:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &inp.p, &inp.q, &inp.c);
^

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 600 / 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 917 ms 29744 KB
03.txt 1592 ms 66736 KB
04.txt 1596 ms 65072 KB
05.txt 1403 ms 54064 KB
06.txt 518 ms 36276 KB
07.txt 604 ms 37684 KB
08.txt 1406 ms 66480 KB
09.txt 628 ms 41012 KB
10.txt 658 ms 40884 KB
11.txt 781 ms 42032 KB
12.txt 251 ms 17568 KB
13.txt 569 ms 26672 KB
14.txt 757 ms 40624 KB
15.txt 664 ms 36272 KB
16.txt 755 ms 39984 KB
17.txt 827 ms 42928 KB
18.txt 433 ms 22064 KB
19.txt 728 ms 38576 KB
20.txt 832 ms 44720 KB
21.txt 1409 ms 62000 KB
22.txt 865 ms 46256 KB
23.txt 999 ms 52144 KB
24.txt 788 ms 41904 KB
25.txt 244 ms 15240 KB
26.txt 530 ms 25008 KB
27.txt 794 ms 42672 KB
28.txt 773 ms 42032 KB
29.txt 800 ms 44080 KB
30.txt 763 ms 40496 KB
31.txt 554 ms 26928 KB
32.txt 721 ms 38960 KB
33.txt 810 ms 44336 KB
34.txt 662 ms 34992 KB
35.txt 230 ms 19592 KB
36.txt 447 ms 21936 KB
37.txt 696 ms 35760 KB
38.txt 679 ms 34480 KB
sample_01.txt 4 ms 256 KB
sample_02.txt 4 ms 256 KB
sample_03.txt 4 ms 256 KB
w1.txt 757 ms 40496 KB
w10.txt 1423 ms 58160 KB
w11.txt 266 ms 15776 KB
w12.txt 528 ms 19760 KB
w13.txt 1049 ms 32816 KB
w14.txt 1328 ms 53936 KB
w15.txt 176 ms 17908 KB
w16.txt 283 ms 17160 KB
w17.txt 503 ms 19376 KB
w18.txt 859 ms 26800 KB
w2.txt 808 ms 40368 KB
w3.txt 1036 ms 48304 KB
w4.txt 812 ms 39600 KB
w5.txt 1349 ms 66352 KB
w6.txt 1101 ms 54832 KB
w7.txt 1040 ms 55088 KB
w8.txt 1312 ms 54448 KB
w9.txt 1386 ms 55344 KB