CSES - Flight Discount

Solution 1 by Kai Wang

Say I use the discount coupon on the edge between cities A and B.

There are two cases: I can go from $1\to A\to B\to N$, or $1\to B\to A\to N$. We need to know the distance between $1$ and $A$, and $N$ and $B$.

We can use Dijkstra's to compute the distance from $1$ and $N$ to every vertex. Then our answer is ${\text{min}}_{A\to B}dist1[A]+c(A,B)+distN[B]$, where $c(A,B)$ is the cost to travel from city A to city B after applying the coupon to that flight.

1import java.io.*; 
2import java.util.*;
3
4public class FlightDiscount {
5
6    /**
7     * Author : Kai Wang
8     */
9    static class Pair implements Comparable<Pair>{
10        int v; long w;

Solution 2 by Stanley Zhong

Alternatively, we can run Dijkstra's and modify our distance array slightly to track whether the discount has been used or not.

$dist[i][0]$ will represent the shortest distance from the start node to node $i$, without using the discount. $dist[i][1]$ will represent the shortest distance after using the discount.

1// Author: Stanley Zhong
2#include <bits/stdc++.h>
3using namespace std;
4
5using ll = long long;
6using pll = pair<ll,ll>;
7#define f first
8#define s second
9
10// create a struct to store data in a priority_queue