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\rightarrow A\rightarrow B\rightarrow N$, or $1\rightarrow B\rightarrow A\rightarrow 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\rightarrow 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.

import java.io.*; 
import java.util.*;

public class FlightDiscount {

	/**
	 * Author : Kai Wang
	 */
	static class Pair implements Comparable<Pair>{
		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.

// Author: Stanley Zhong
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll,ll>;
#define f first
#define s second

// create a struct to store data in a priority_queue