Submission #3229574


Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <unordered_map>
#include <random>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

int N,M,V;
vector<pii> E[800500];
int timer = 0;
int dist[800500];
int main(){
	scanf("%d%d",&N,&M);
	timer = N;
	map<pii,int> mp;
	mp[{1,-1}] = ++timer; E[mp[{1,-1}]].push_back({1,0});
	int st = timer;
	mp[{N,-1}] = ++timer; E[N].push_back({mp[{N,-1}],0});
	int en = timer;


	for(int i=1;i<=M;i++){
		int x,y,z; scanf("%d%d%d",&x,&y,&z);
		
		// x->y
		int v = ++timer;
		E[x].push_back({v,1}); E[y].push_back({v,1});
		E[v].push_back({x,0}); E[v].push_back({y,0});

		if( mp[{x,z}] == 0 ) mp[{x,z}] = ++timer;
		E[mp[{x,z}]].push_back({v,0});
		E[v].push_back({ mp[{x,z}], 0} );
	}

	int V = timer;
	for(int i=1;i<=timer;i++) dist[i] = 1e9;
	dist[st] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, st});

	while( !pq.empty() ){
		int cur = pq.top().Se, curd = pq.top().Fi;
		pq.pop();
		if( dist[cur] < curd ) continue;
		for(auto e : E[cur]){
			if( dist[e.Fi] > dist[cur]+e.Se ){
				dist[e.Fi] = dist[cur]+e.Se;
				pq.push({dist[e.Fi],e.Fi});
			}
		}
	}

	printf("%d\n",dist[en]<1e8?dist[en]:-1);
}











Submission Info

Submission Time
Task E - Snuke's Subway Trip
User kjp4155
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1708 Byte
Status WA
Exec Time 503 ms
Memory 57204 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:36:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&M);
                     ^
./Main.cpp:46:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int x,y,z; scanf("%d%d%d",&x,&y,&z);
                                      ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status AC
AC × 31
WA × 28
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 8 ms 20096 KB
02.txt WA 341 ms 46584 KB
03.txt AC 493 ms 56828 KB
04.txt AC 353 ms 55680 KB
05.txt WA 458 ms 53496 KB
06.txt WA 154 ms 38400 KB
07.txt WA 209 ms 40448 KB
08.txt AC 503 ms 56824 KB
09.txt AC 215 ms 40960 KB
10.txt AC 213 ms 40960 KB
11.txt AC 167 ms 39924 KB
12.txt AC 133 ms 38012 KB
13.txt AC 150 ms 38772 KB
14.txt WA 182 ms 40440 KB
15.txt AC 165 ms 38532 KB
16.txt WA 181 ms 40184 KB
17.txt WA 172 ms 39540 KB
18.txt AC 142 ms 38772 KB
19.txt AC 160 ms 39660 KB
20.txt WA 189 ms 40184 KB
21.txt AC 367 ms 54648 KB
22.txt WA 187 ms 40052 KB
23.txt WA 263 ms 46200 KB
24.txt AC 164 ms 39536 KB
25.txt AC 127 ms 37748 KB
26.txt AC 152 ms 38636 KB
27.txt AC 182 ms 39544 KB
28.txt AC 166 ms 39552 KB
29.txt AC 180 ms 39552 KB
30.txt AC 165 ms 39564 KB
31.txt AC 147 ms 38512 KB
32.txt AC 148 ms 39528 KB
33.txt AC 191 ms 39808 KB
34.txt WA 185 ms 40056 KB
35.txt AC 127 ms 37748 KB
36.txt AC 148 ms 39024 KB
37.txt WA 210 ms 41076 KB
38.txt WA 190 ms 40052 KB
sample_01.txt AC 8 ms 20096 KB
sample_02.txt AC 8 ms 20096 KB
sample_03.txt AC 8 ms 20096 KB
w1.txt WA 187 ms 39760 KB
w10.txt AC 390 ms 54784 KB
w11.txt WA 167 ms 36044 KB
w12.txt WA 230 ms 38144 KB
w13.txt WA 361 ms 46976 KB
w14.txt AC 368 ms 53760 KB
w15.txt WA 121 ms 35776 KB
w16.txt WA 158 ms 36096 KB
w17.txt WA 209 ms 37376 KB
w18.txt WA 301 ms 43648 KB
w2.txt WA 191 ms 40520 KB
w3.txt WA 324 ms 48500 KB
w4.txt WA 288 ms 45928 KB
w5.txt AC 451 ms 57204 KB
w6.txt WA 327 ms 48756 KB
w7.txt WA 406 ms 53320 KB
w8.txt WA 410 ms 53120 KB
w9.txt WA 392 ms 53888 KB