test/yosupo_shortest_path.cpp

• View this file on GitHub
• Last update: 2024-05-10 22:05:31+09:00
• Problem: https://judge.yosupo.jp/problem/shortest_path

Depends on

• Dijkstra(経路復元付ダイクストラ) (graph/dijkstra.cpp)
• 2D-Array( $2$ 次元配列) (structure/2d_array.cpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/shortest_path

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#include "graph/dijkstra.cpp"

int main() {
	int N, M, s, t;
	cin >> N >> M >> s >> t;
	v2d<int> path(N, 0), cost(N, 0);
	for(int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		path[a].push_back(b);
		cost[a].push_back(c);
	}

	dijkstra dijk(path, cost, s);
	auto ans = dijk.get_path(t);

	if(ans.size() == 1) {
		cout << -1 << endl;
		return 0;
	}

	cout << dijk[t] << " " << ans.size() - 1 << endl;
	for(int i = 0; i < ans.size() - 1; i++) {
		cout << ans[i] << " " << ans[i + 1] << endl;
	}
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 422, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: test/yosupo_shortest_path.cpp: line 9: found codes out of include guard

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	670 ms	35 MB
g++	almost_line_01	AC	682 ms	35 MB
g++	almost_line_02	AC	561 ms	35 MB
g++	example_00	AC	6 ms	3 MB
g++	example_01	AC	5 ms	3 MB
g++	grid_random_00	AC	428 ms	18 MB
g++	grid_swirl_00	AC	529 ms	20 MB
g++	line_00	AC	1019 ms	68 MB
g++	max_dense_long_00	AC	289 ms	9 MB
g++	max_dense_random_00	AC	282 ms	9 MB
g++	max_dense_random_01	AC	286 ms	9 MB
g++	max_dense_zero_00	AC	198 ms	9 MB
g++	max_sparse_random_00	AC	456 ms	32 MB
g++	max_sparse_random_01	AC	511 ms	33 MB
g++	max_sparse_random_02	AC	496 ms	33 MB
g++	max_star_00	AC	413 ms	46 MB
g++	max_star_01	AC	546 ms	55 MB
g++	small_00	AC	6 ms	3 MB
g++	small_01	AC	5 ms	3 MB
g++	small_02	AC	5 ms	3 MB
g++	small_03	AC	5 ms	3 MB
g++	small_04	AC	5 ms	3 MB
g++	sparse_random_00	AC	383 ms	42 MB
g++	sparse_random_01	AC	387 ms	47 MB
g++	sparse_random_02	AC	303 ms	14 MB
g++	spfa_killer_00	AC	563 ms	41 MB
g++	wrong_dijkstra_handmade_00	AC	6 ms	3 MB
g++	wrong_dijkstra_killer_00	AC	419 ms	40 MB
g++	wrong_dijkstra_killer_01	AC	711 ms	46 MB
clang++	almost_line_00	AC	605 ms	35 MB
clang++	almost_line_01	AC	600 ms	35 MB
clang++	almost_line_02	AC	523 ms	35 MB
clang++	example_00	AC	6 ms	3 MB
clang++	example_01	AC	5 ms	3 MB
clang++	grid_random_00	AC	409 ms	18 MB
clang++	grid_swirl_00	AC	526 ms	20 MB
clang++	line_00	AC	994 ms	68 MB
clang++	max_dense_long_00	AC	286 ms	9 MB
clang++	max_dense_random_00	AC	278 ms	9 MB
clang++	max_dense_random_01	AC	305 ms	9 MB
clang++	max_dense_zero_00	AC	198 ms	9 MB
clang++	max_sparse_random_00	AC	503 ms	32 MB
clang++	max_sparse_random_01	AC	517 ms	33 MB
clang++	max_sparse_random_02	AC	489 ms	33 MB
clang++	max_star_00	AC	415 ms	46 MB
clang++	max_star_01	AC	534 ms	55 MB
clang++	small_00	AC	6 ms	3 MB
clang++	small_01	AC	5 ms	3 MB
clang++	small_02	AC	5 ms	3 MB
clang++	small_03	AC	5 ms	3 MB
clang++	small_04	AC	5 ms	3 MB
clang++	sparse_random_00	AC	373 ms	42 MB
clang++	sparse_random_01	AC	387 ms	47 MB
clang++	sparse_random_02	AC	312 ms	14 MB
clang++	spfa_killer_00	AC	530 ms	42 MB
clang++	wrong_dijkstra_handmade_00	AC	6 ms	3 MB
clang++	wrong_dijkstra_killer_00	AC	421 ms	41 MB
clang++	wrong_dijkstra_killer_01	AC	730 ms	46 MB

Back to top page