Submission #3230606


Source Code Expand

#include <bits/stdc++.h>

using namespace std ;

#define N 5000010
#define inf 0x3f3f3f3f

int head[ N ] , cnt ;
int d[ N ] , vis[ N ] , q[ N ] ;
int n , m ;
struct node {
	int to , nxt , v ;
}e[ N ] ; 

void ins( int u , int v , int w ) {
	e[ ++ cnt ].to = v ;
	e[ cnt ].nxt = head[ u ] ;
	e[ cnt ].v = w ;
	head[ u ] = cnt ;
} 

map<pair<int,int>,int>mp;

int tot = 0 ;

int get_num( int x , int y ) {
	if( !mp.count( make_pair( x , y ) ) ) mp[ make_pair( x , y ) ] = ++tot ;
	return mp[ make_pair( x , y ) ] ;
}

void spfa() {
	for( int i = 1 ; i <= tot ; i ++ ) d[ i ] = inf ;
	vis[ 1 ] = q[ 1 ] = 1 ;
	d[ 1 ] = 0 ;
	int l = 1 , r = 2 ;
	while( l < r ) {
		int u = q[ l ++ ] ;
		vis[ u ] = 0 ;
		for( int i = head[ u ] ; i ; i = e[ i ].nxt ) {
			int v = e[ i ].to ;
			if( d[ v ] > d[ u ] + e[ i ].v ) {
				d[ v ] = d[ u ] + e[ i ].v ;
				if( !vis[ v ] ) vis[ v ] = 1 , q[ r ++ ] = v ;
			}
		}
	}
	if( d[ n ] == inf ) puts( "-1" ) ;
	else printf( "%d\n" , d[ n ] / 2 ) ;
}

int main() {
	scanf( "%d%d" , &n , &m ) ;
	tot = n ;
	for( int i = 1 ; i <= m ; i ++ ) {
		int x , y , c ;
		scanf( "%d%d%d" , &x , &y , &c ) ;
		int n1 = get_num( x , c ) , n2 = get_num( y , c ) ;
		ins( x , n1 , 1 ) ;
		ins( n1 , x , 1 ) ;
		ins( n1 , y , 1 ) ;
		ins( y , n1 , 1 ) ;
		ins( n1 , n2 , 0 ) ;
		ins( n2 , n1 , 0 ) ;
	}
	spfa() ;
}

Submission Info

Submission Time
Task E - Snuke's Subway Trip
User henry_y
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1393 Byte
Status AC
Exec Time 382 ms
Memory 55936 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:52:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf( "%d%d" , &n , &m ) ;
                            ^
./Main.cpp:56:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf( "%d%d%d" , &x , &y , &c ) ;
                                    ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status AC
AC × 59
Set Name Test Cases
Sample
All 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, sample_01.txt, sample_02.txt, sample_03.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 AC 3 ms 8448 KB
02.txt AC 262 ms 29952 KB
03.txt AC 382 ms 55936 KB
04.txt AC 351 ms 51712 KB
05.txt AC 345 ms 44032 KB
06.txt AC 138 ms 32256 KB
07.txt AC 156 ms 32384 KB
08.txt AC 364 ms 55936 KB
09.txt AC 169 ms 34560 KB
10.txt AC 169 ms 34560 KB
11.txt AC 196 ms 36736 KB
12.txt AC 82 ms 22784 KB
13.txt AC 158 ms 27392 KB
14.txt AC 192 ms 35968 KB
15.txt AC 157 ms 30208 KB
16.txt AC 180 ms 34816 KB
17.txt AC 197 ms 37120 KB
18.txt AC 123 ms 24064 KB
19.txt AC 178 ms 34816 KB
20.txt AC 208 ms 38144 KB
21.txt AC 332 ms 54784 KB
22.txt AC 231 ms 39296 KB
23.txt AC 266 ms 42880 KB
24.txt AC 193 ms 37888 KB
25.txt AC 77 ms 22912 KB
26.txt AC 143 ms 27392 KB
27.txt AC 204 ms 39296 KB
28.txt AC 194 ms 38144 KB
29.txt AC 199 ms 38784 KB
30.txt AC 188 ms 37120 KB
31.txt AC 149 ms 28160 KB
32.txt AC 173 ms 34816 KB
33.txt AC 203 ms 39040 KB
34.txt AC 168 ms 30336 KB
35.txt AC 71 ms 22784 KB
36.txt AC 123 ms 24064 KB
37.txt AC 179 ms 30848 KB
38.txt AC 169 ms 30208 KB
sample_01.txt AC 3 ms 8448 KB
sample_02.txt AC 3 ms 8448 KB
sample_03.txt AC 2 ms 6400 KB
w1.txt AC 194 ms 34944 KB
w10.txt AC 362 ms 51840 KB
w11.txt AC 114 ms 22912 KB
w12.txt AC 171 ms 24064 KB
w13.txt AC 274 ms 35584 KB
w14.txt AC 353 ms 49536 KB
w15.txt AC 70 ms 22784 KB
w16.txt AC 102 ms 22784 KB
w17.txt AC 145 ms 23296 KB
w18.txt AC 224 ms 27776 KB
w2.txt AC 189 ms 34816 KB
w3.txt AC 241 ms 38912 KB
w4.txt AC 191 ms 31104 KB
w5.txt AC 358 ms 55680 KB
w6.txt AC 277 ms 44288 KB
w7.txt AC 351 ms 51584 KB
w8.txt AC 366 ms 51840 KB
w9.txt AC 368 ms 51968 KB