The idea is to use Dijkstra for finding shortest path as following:

- Find maximum value (maxVal) in days.
- maxVal += 1
- Subtract all days values from maxVal
- Now we can use Dijkstra to find the shortest path. We can easily compute neighbors based on flights.
- Note: Updating an element in PriorityQueue requires O(n), this is why instead I use the trick in the NOTE in page 2 here: https://activities.tjhsst.edu/sct/lectures/1314/dijkstra_10_30_13.pdf.
- At the end, return numberOfWeeks * maxValue - shortest Path value.

```
private Comparator<int[]> StateComparator = new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
assert a != null && b != null;
return a[0] - b[0];
}
};
public int maxVacationDays(int[][] flights, int[][] days) {
int maxVal = 0;
for (int i = 0; i < days.length; i++) {
for (int j = 0; j < days[i].length; j++) {
if (days[i][j] > maxVal)
maxVal = days[i][j];
}
}
maxVal++;
for (int i = 0; i < days.length; i++) {
for (int j = 0; j < days[i].length; j++) {
days[i][j] = maxVal - days[i][j];
}
}
int cities = days.length;
int weeks = days[0].length;
boolean[][] visited = new boolean[cities][weeks];
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(cities, StateComparator);
for (int city = 0; city < cities; city++) {
if (city == 0 || flights[0][city] == 1)
pq.add(new int[] { days[city][0], city, 0 });
}
while (!pq.isEmpty()) {
int[] min = pq.peek();
pq.remove();
int dist = min[0];
int city = min[1];
int week = min[2];
if (visited[city][week])
continue;
visited[city][week] = true;
int nextWeek = week + 1;
if (nextWeek == weeks) // stop condition
return weeks * maxVal - dist;
for (int nextCity = 0; nextCity < cities; nextCity++) {
if (city == nextCity || flights[city][nextCity] == 1)
pq.add(new int[] { dist + days[nextCity][nextWeek], nextCity, nextWeek });
}
}
assert false;
return 0;
}
```