The first thing we do is reverse engineer the bounds of the problem. Since K is large, we almost certainly need an algorithm which computes the cost of traveling between all pairs of vertices. Given N = 250, we expect a roughly O(N3) algorithm for all-pairs shortest paths. The two most common O(N3) all-pairs shortest path algorithms are Floyd–Warshall and N iterations of O(N2) Dijkstra. So we probably will want some sort of modified Floyd–Warshall or modified Dijkstra.
It is not obvious how to handle all of the different vertex tolls, since these don't fit into the standard shortest path problem. However, look at the problem differently. Suppose that we had already committed to paying a vertex toll of 15 but no more. Then, we could choose any path which used vertices with a vertex cost of at most 15, but no vertices with a vertex cost greater than 15. The optimal solution would be the path with the smallest total edge toll among all paths which use only vertices with a vertex toll of at most 15.
Of course, we don't know what vertex toll we're going to end up paying, but we do know that it will be equal to the toll of one of the vertices in the graph. The presents an idea: for each of the N possible vertex tolls, we run an O(N3) all-pairs shortest path algorithm in which we only use vertices cheaper than our chosen toll. We then take the cheapest paths from all N runs. The problem: this algorithm is O(N4).
Let's think about Floyd–Warshall some more. Floyd–Warshall is interesting because it's an all-pairs shortest path algorithm which already works by adding one vertex at a time to the graph. Part way through the algorithm, the shortest paths found are the shortest paths that use only some of the vertices in the graph. This gives us an idea: we first sort the vertices in increasing order of vertex cost. We then run Floyd–Warshall, considering the vertices of the graph in that order for the outer loop. After i iterations of Floyd–Warshall, we will have the cheapest path with vertex toll equal to the i-th largest vertex toll in the graph. Thus, after each iteration, we add the i-th vertex toll to the edge cost of each path and see if we get any paths with smaller total costs than the best paths found so far. The cheapest path between any two vertices is the cheapest of all of the intermediate paths found after each iteration of Floyd-Warshall.
#include <stdlib.h>
#include <stdio.h>
template <class t> inline t max(const t& a, const t& b, const t& c) {
if(a > b) {
if(a > c) { return(a); }
else { return(c); }
} else {
if(b > c) { return(b); }
else { return(c); }
}
}
const int MAXN = 1000;
const int BIG = 1000000000;
int n,m,k;
int vcost[MAXN];
int dist[MAXN][MAXN];
int cost[MAXN][MAXN];
int vidx[MAXN];
int main() {
// Read input
FILE* fin = fopen ("toll.in", "r");
fscanf (fin, "%d %d %d", &n, &m, &k);
for (int i = 0; i < n; ++i) {
fscanf (fin, "%d", &vcost[i]);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dist[i][j] = BIG;
cost[i][j] = BIG;
}
dist[i][i] = 0;
}
for (int i = 0; i < m; ++i) {
int a,b,l;
fscanf (fin, "%d %d %d", &a, &b, &l);
--a; --b; // 1 -> 0 based indexes
if(dist[a][b] > l) {
dist[a][b] = l;
dist[b][a] = l;
}
}
// Sort vertices by increasing vertex weight
for (int i = 0; i < n; ++i) {
vidx[i] = i;
}
for (int i = 0; i < n; ++i) {
for (int j = i; j > 0 && vcost[vidx[j]] < vcost[vidx[j-1]]; --j) {
int s = vidx[j];
vidx[j] = vidx[j-1];
vidx[j-1] = s;
}
}
// Modified Floyd-Warshall
for (int p = 0; p < n; ++p) {
int k = vidx[p];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dist[i][j] >= dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
if (cost[i][j] > dist[i][j] + max(vcost[k], vcost[i], vcost[j])) {
cost[i][j] = dist[i][j] + max(vcost[k], vcost[i], vcost[j]);
}
}
}
}
}
// Output answers
FILE* fout = fopen("toll.out", "w");
for (int i = 0; i < k; ++i) {
int a,b;
fscanf (fin, "%d %d", &a, &b);
--a; --b; // 1 -> 0 based indexes
fprintf (fout, "%d\n", cost[a][b]);
}
fclose (fout);
fclose (fin);
return (0);
}