Solution 1

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

There are two cases: we 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 $\min\limits_{A\rightarrow B} \texttt{dist1}[A]+c(A,B)+\texttt{distN}[B]$, where $c(A,B)$ is the cost to travel from city $A$ to city $B$ after applying the coupon to that flight, $\texttt{dist1}[A]$ is the cost to travel from city $1$ to city $A$ and $\texttt{distN}[B]$ is the cost to travel from city $B$ to city $N$.

Copy
#include <iostream>
#include <queue>
#include <vector>

using std::cout;
using std::endl;
using std::pair;
using std::vector;

/**

Solution 2

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

$\texttt{dist}[i][\texttt{false}]$ will represent the shortest distance from the start node to node $i$, without using the discount. $\texttt{dist}[i][\texttt{true}]$ will represent the shortest distance after using the discount.

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

public class FlightDiscount {
	static ArrayList<int[]>[] adj;

	// dist[i][0] = shortest distance to node i without using discount
	// dist[i][1] = shortest distance to node i after using discount
	static long[][] dist;
	static final long INF = (long)1e18;