Submission #8036357


Source Code Expand

Copy
#include <bits/stdc++.h>

int main()
{
	using vi = std::vector<int64_t>;
	using vvi = std::vector<vi>;
	int N, M;
	int64_t L;
	scanf("%d%d%lld", &N, &M, &L);
	vvi distance(N, vi(N, 1ll << 60));
	for (int i{}; i < M; i++)
	{
		int A, B, C;
		scanf("%d%d%d", &A, &B, &C);
		A--; B--;
		distance[A][B] = distance[B][A] = C;
	}
	for (int i{}; i < N; i++)
		distance[i][i] = 0;
	for (int mid{}; mid < N; mid++)
		for (int from{}; from < N; from++)
			for (int to{}; to < N; to++)
				distance[from][to] = std::min(distance[from][to], distance[from][mid] + distance[mid][to]);
	
	vvi gasoline(N, vi(N, N + 1));
	for (int from{}; from < N; from++)
	{
		std::queue<int> bfs;
		bfs.push(from);
		for (int next{}; next < N; next++)
		{
			if (distance[from][next] > L) continue;
			gasoline[from][next] = 0;
			bfs.push(next);
		}
		while (!bfs.empty())
		{
			auto now{bfs.front()};
			bfs.pop();
			for (int next{}; next < N; next++)
			{
				if (distance[now][next] > L) continue;
				if (gasoline[from][next] <= gasoline[from][now] + 1) continue;
				gasoline[from][next] = gasoline[from][now] + 1;
				bfs.push(next);
			}
		}
	}
	int Q;
	scanf("%d", &Q);
	for (int i{}; i < Q; i++)
	{
		int s, t;
		scanf("%d%d", &s, &t);
		s--; t--;
		if (gasoline[s][t] == N + 1)
			puts("-1");
		else
			printf("%lld\n", gasoline[s][t]);
	}
	// for (auto& e: gasoline)
	// {
	// 	for (auto& f: e)
	// 		std::cout << f << ' ';
	// 	std::cout << std::endl;
	// }

	return 0;
}

Submission Info

Submission Time
Task E - Travel by Car
User TanakaTaroh
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1524 Byte
Status AC
Exec Time 126 ms
Memory 1920 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:9:30: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 4 has type ‘int64_t* {aka long int*}’ [-Wformat=]
  scanf("%d%d%lld", &N, &M, &L);
                              ^
./Main.cpp:59:35: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long int> >::value_type {aka long int}’ [-Wformat=]
    printf("%lld\n", gasoline[s][t]);
                                   ^
./Main.cpp:9:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &N, &M, &L);
                               ^
./Main.cpp:14:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &A, &B, &C);
                              ^
./Main.cpp:50:17: warning: ignoring return value of ‘int scanf(const char*, .....

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 50
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 02-random-08, 02-random-09, 02-random-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39, 02-random-40, 02-random-41, 02-random-42, 02-random-43, 02-random-44, 02-random-45, 02-random-46, 02-random-47, 02-random-48, 02-random-49
Case Name Status Exec Time Memory
00-sample-00 AC 1 ms 256 KB
00-sample-01 AC 1 ms 256 KB
00-sample-02 AC 1 ms 256 KB
01-handmade-03 AC 47 ms 1920 KB
01-handmade-04 AC 126 ms 1792 KB
01-handmade-05 AC 126 ms 1792 KB
01-handmade-06 AC 110 ms 1920 KB
01-handmade-07 AC 111 ms 1920 KB
02-random-08 AC 2 ms 256 KB
02-random-09 AC 5 ms 384 KB
02-random-10 AC 115 ms 1920 KB
02-random-11 AC 4 ms 384 KB
02-random-12 AC 10 ms 512 KB
02-random-13 AC 10 ms 512 KB
02-random-14 AC 82 ms 1408 KB
02-random-15 AC 51 ms 1920 KB
02-random-16 AC 44 ms 896 KB
02-random-17 AC 57 ms 1280 KB
02-random-18 AC 4 ms 384 KB
02-random-19 AC 1 ms 256 KB
02-random-20 AC 113 ms 1920 KB
02-random-21 AC 19 ms 640 KB
02-random-22 AC 1 ms 256 KB
02-random-23 AC 39 ms 768 KB
02-random-24 AC 99 ms 1536 KB
02-random-25 AC 117 ms 1920 KB
02-random-26 AC 2 ms 256 KB
02-random-27 AC 20 ms 1024 KB
02-random-28 AC 47 ms 1024 KB
02-random-29 AC 39 ms 896 KB
02-random-30 AC 52 ms 1920 KB
02-random-31 AC 5 ms 384 KB
02-random-32 AC 28 ms 896 KB
02-random-33 AC 37 ms 896 KB
02-random-34 AC 28 ms 768 KB
02-random-35 AC 112 ms 1920 KB
02-random-36 AC 17 ms 768 KB
02-random-37 AC 50 ms 896 KB
02-random-38 AC 1 ms 256 KB
02-random-39 AC 2 ms 256 KB
02-random-40 AC 112 ms 1920 KB
02-random-41 AC 112 ms 1792 KB
02-random-42 AC 7 ms 512 KB
02-random-43 AC 94 ms 1536 KB
02-random-44 AC 1 ms 256 KB
02-random-45 AC 51 ms 1920 KB
02-random-46 AC 7 ms 384 KB
02-random-47 AC 69 ms 1408 KB
02-random-48 AC 1 ms 256 KB
02-random-49 AC 8 ms 384 KB