Submission #1987955


Source Code Expand

# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = 1e17 - 10;
const double PI = acos(-1);
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, LL> Vec2;
typedef tuple<LL, LL, LL> Tll;
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,n) for(LL i=n-1;i>=0;i--)
struct Edge { LL to, cost; };
vector<Edge>vec[1100000];
LL h, w, n, m, s, t, sum, ans = 0, d[1100000], mn;
void DIUX(LL s) {
	rep(i,1100000) d[i] = INF;
	d[s] = 0;
	priority_queue<Ppll, vector<Ppll>, greater<Ppll>> pq;
	pq.push(make_pair(d[s], Pll(s, 0))); // (cost,頂点番号) 
	while (!pq.empty()) {
		Ppll pp;
		pp = pq.top();
		LL cos = pp.first, vv = pp.second.first, nn = pp.second.second;
		pq.pop();
		if (d[vv] < pp.first)continue;
		if (nn != 0 && cos + 1 < d[vv]) {
			d[vv] = cos + 1;
			pq.push(make_pair(d[vv], Pll(vv, 0)));
		}
		rep(i, vec[vv].size()) {
			if ((nn == vec[vv][i].cost || nn == 0) && cos+1 < d[vec[vv][i].to]) {
				pq.push(make_pair(cos, Pll(vec[vv][i].to, vec[vv][i].cost)));
			}
		}
	}
}

int main() {
	cin >> n >> m;
	rep(i, m) {
		cin >> s >> t >> w;
		vec[s].push_back(Edge{ t,w });
		vec[t].push_back(Edge{ s,w });
	}
	DIUX(1);
	mn = d[n];
	cout << (mn == INF ? -1 : mn) << endl;
	return 0;
}

Submission Info

Submission Time
Task E - Snuke's Subway Trip
User akusyounin
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1894 Byte
Status RE
Exec Time 3161 ms
Memory 1618348 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status AC
AC × 37
WA × 11
TLE × 10
RE × 1
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 13 ms 34688 KB
02.txt AC 145 ms 43520 KB
03.txt AC 280 ms 46712 KB
04.txt AC 208 ms 45056 KB
05.txt WA 257 ms 46712 KB
06.txt AC 108 ms 39296 KB
07.txt AC 149 ms 41024 KB
08.txt AC 292 ms 46968 KB
09.txt AC 154 ms 41152 KB
10.txt AC 154 ms 41152 KB
11.txt AC 225 ms 51436 KB
12.txt TLE 3161 ms 1617484 KB
13.txt AC 295 ms 56424 KB
14.txt AC 220 ms 46196 KB
15.txt AC 253 ms 57448 KB
16.txt WA 224 ms 46368 KB
17.txt WA 209 ms 47728 KB
18.txt TLE 3161 ms 1616972 KB
19.txt AC 257 ms 57960 KB
20.txt AC 240 ms 50696 KB
21.txt AC 227 ms 46576 KB
22.txt WA 219 ms 50540 KB
23.txt AC 236 ms 46964 KB
24.txt AC 207 ms 46448 KB
25.txt TLE 3157 ms 437204 KB
26.txt AC 263 ms 56168 KB
27.txt AC 219 ms 47220 KB
28.txt WA 216 ms 51180 KB
29.txt AC 223 ms 51228 KB
30.txt AC 213 ms 46960 KB
31.txt AC 266 ms 57448 KB
32.txt AC 204 ms 48624 KB
33.txt AC 220 ms 46348 KB
34.txt WA 223 ms 50412 KB
35.txt RE 2547 ms 1617612 KB
36.txt AC 767 ms 94176 KB
37.txt WA 244 ms 51056 KB
38.txt WA 225 ms 50412 KB
sample_01.txt AC 13 ms 34560 KB
sample_02.txt AC 13 ms 34560 KB
sample_03.txt AC 13 ms 34560 KB
w1.txt TLE 3159 ms 1617576 KB
w10.txt AC 207 ms 44928 KB
w11.txt TLE 3157 ms 436116 KB
w12.txt TLE 3157 ms 142624 KB
w13.txt WA 180 ms 43392 KB
w14.txt AC 187 ms 44928 KB
w15.txt TLE 3157 ms 436272 KB
w16.txt TLE 3159 ms 1617552 KB
w17.txt TLE 3157 ms 438628 KB
w18.txt WA 207 ms 45056 KB
w2.txt TLE 3159 ms 1618348 KB
w3.txt AC 273 ms 48880 KB
w4.txt AC 300 ms 52716 KB
w5.txt AC 292 ms 48880 KB
w6.txt AC 263 ms 48880 KB
w7.txt WA 2019 ms 41948 KB
w8.txt AC 411 ms 42496 KB
w9.txt AC 238 ms 43392 KB