IntermediateDijkstra practice · C++17Best score: not submitted
Client-side educational grading. Submit runs your C++17 program against ten predefined tests in your browser. Tests are intentionally visible through See Hidden Tests. Scores are local practice records, not secure competition results.
Grading tests
C++ Suggestion Library
main.cpp · C++17
Loading Monaco Editor…
Loading this problem’s draft…
Ctrl / ⌘ + Enter runs your custom test. Input limit: 1 MiB.
Loading editor…
Standard Output
Standard Error
Compiler Diagnostics
Submission results
Ten tests, ten points each. Output is checked against the expected answer. Custom runs never change your score.
Test
Result
Points
Execution time
Each test has a 5-second execution limit, 256 MiB linked program WASM memory maximum, and 1 MiB combined output limit. Allocated WASM memory is not peak browser memory. Deep recursion can overflow the WASM stack; an iterative traversal is safer for long paths.
Problem statement
You are given a directed weighted graph with N vertices and M edges. You must travel from S to T. You have a coupon that can be used on at most one edge. When used, that edge's cost becomes floor(W / 2). Find the minimum possible total travel cost. If T is unreachable, print -1. Self-loops and repeated edges are allowed.
Input format
First line: N M. Next M lines: U V W. Last line: S T.
Output format
Print the minimum total cost.
Constraints
1 ≤ N ≤ 100000
0 ≤ M ≤ 200000
1 ≤ U, V, S, T ≤ N
0 ≤ W ≤ 10^9
Use 64-bit integers for route costs.
Sample input
4 4
1 2 8
2 4 6
1 3 5
3 4 10
1 4
Sample output
10
Sample explanation
Use the coupon on 1 → 2: floor(8 / 2) + 6 = 10. Using it on 3 → 4 also gives 5 + floor(10 / 2) = 10.
Need a hint?
Dijkstra with two states per vertex: - dist[v][0]: minimum cost reaching v without using the coupon. - dist[v][1]: minimum cost reaching v after using the coupon. The answer is min(dist[T][0], dist[T][1]). Expected complexity: O((N + M) log N).