Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Your situation at any moment is (city, have I used the coupon yet?) — that's only 2n states.
  2. 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;
    }
}

Solve One Free Ride online · All practice problems