Practice › Graphs
One Free Ride
Hard · Graphs
There are n cities and m one-way roads; road u v w goes from city u to city v and costs w. You start in city 1 and want to reach city n. You have one coupon that makes a single road of your choice free. Print the minimum total cost, or -1 if city n cannot be reached.
Input
First line: n m. Next m lines: u v w.
Output
The minimum cost, or -1.
Constraints
- 2 ≤ n ≤ 10^5
- 0 ≤ m ≤ 2·10^5
- 1 ≤ w ≤ 10^9
The answer can exceed the 32-bit range. Using the coupon is optional.
Example 1
Input
4 4 1 2 5 2 4 10 1 3 2 3 4 20
Output
2
Example 2
Input
3 1 2 3 4
Output
-1
Hints
- Your situation at any moment is (city, have I used the coupon yet?) — that's only 2n states.
- Run Dijkstra on these states. From (u, unused) a road u→v can be paid normally → (v, unused), or taken free → (v, used). From (u, used) roads are always paid.
Approach
Build a "layered" graph: layer 0 means the coupon is still available, layer 1 means it's been used. Every road u → v with cost w gives the edges (u,0) → (v,0) with cost w, (u,1) → (v,1) with cost w, and (u,0) → (v,1) with cost 0 (the free ride). All weights are non-negative, so Dijkstra from (1, 0) works directly. The answer is min(dist[n][0], dist[n][1]), since using the coupon is optional, or -1 if both are ∞. Costs reach about 2·10^14, so use 64-bit distances.
Complexity: O((n + m) log n) time · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, long long>>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
const long long INF = LLONG_MAX;
vector<array<long long, 2>> dist(n + 1, {INF, INF}); // dist[city][coupon used?]
priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq;
dist[1][0] = 0;
pq.push(make_tuple(0LL, 1, 0));
while (!pq.empty()) {
long long d;
int u, used;
tie(d, u, used) = pq.top();
pq.pop();
if (d > dist[u][used]) continue;
for (auto &e : adj[u]) {
int v = e.first;
long long w = e.second;
if (d + w < dist[v][used]) { // pay for this road
dist[v][used] = d + w;
pq.push(make_tuple(dist[v][used], v, used));
}
if (!used && d < dist[v][1]) { // use the coupon here
dist[v][1] = d;
pq.push(make_tuple(d, v, 1));
}
}
}
long long best = min(dist[n][0], dist[n][1]);
cout << (best == INF ? -1 : best) << "\n";
return 0;
}Python solution
import sys
import heapq
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
for i in range(m):
u, v, w = data[2 + 3 * i : 5 + 3 * i]
adj[u].append((v, w))
INF = float("inf")
dist = [[INF, INF] for _ in range(n + 1)] # dist[city][coupon used?]
dist[1][0] = 0
pq = [(0, 1, 0)]
while pq:
d, u, used = heapq.heappop(pq)
if d > dist[u][used]:
continue
for v, w in adj[u]:
if d + w < dist[v][used]: # pay for this road
dist[v][used] = d + w
heapq.heappush(pq, (d + w, v, used))
if not used and d < dist[v][1]: # use the coupon here
dist[v][1] = d
heapq.heappush(pq, (d, v, 1))
best = min(dist[n])
print(-1 if best == INF else best)Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
int n = (int) readLong(in), m = (int) readLong(in);
List<List<long[]>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
int u = (int) readLong(in), v = (int) readLong(in);
long w = readLong(in);
adj.get(u).add(new long[] {v, w});
}
long[][] dist = new long[n + 1][2]; // dist[city][coupon used?]
for (long[] d : dist) Arrays.fill(d, Long.MAX_VALUE);
dist[1][0] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
pq.add(new long[] {0, 1, 0});
while (!pq.isEmpty()) {
long[] top = pq.poll();
long d = top[0];
int u = (int) top[1], used = (int) top[2];
if (d > dist[u][used]) continue;
for (long[] e : adj.get(u)) {
int v = (int) e[0];
if (d + e[1] < dist[v][used]) { // pay for this road
dist[v][used] = d + e[1];
pq.add(new long[] {dist[v][used], v, used});
}
if (used == 0 && d < dist[v][1]) { // use the coupon here
dist[v][1] = d;
pq.add(new long[] {d, v, 1});
}
}
}
long best = Math.min(dist[n][0], dist[n][1]);
System.out.println(best == Long.MAX_VALUE ? -1 : best);
}
// fast reader: the input can have 2·10^5 lines
static long readLong(DataInputStream in) throws IOException {
int c = in.read();
while (c != '-' && (c < '0' || c > '9')) c = in.read();
boolean neg = c == '-';
if (neg) c = in.read();
long x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = in.read();
}
return neg ? -x : x;
}
}