**Analysis: Vacation Planning (gold) by Fatih Gelgi and Demi Guo**

This is an easy shortest path problem for gold division. Since calculating
minimum costs of all pairs with Dijkstra requires O(N (N+M)log N) and with
Floyd-Warshall requires O(N^3), we can't use their trivial implementations.
However from the flight constraint in the problem description, we know that the
minimum cost path between two farms has to go through at least one of the hubs.
Hence, the answer of a request `mincost(a_i,b_i)` is `min_x
{mincost(a_i,x) + mincost(x,b_i)}` where x is a hub. That means we just
need to compute the minimum costs for all hubs. Dijkstra computes the shortest
paths from a single source to all other vertices thus there is no problem when
computing `mincost(x,b_i)`. For `mincost(a_i,x)`, a simple trick
is to reverse the edges of the graph and then compute `mincost(x,a_i)`
for all hubs. The running time is O(K (N+M) log N) and the required memory is O(KN) since
we compute and keep the minimum costs only number of hubs times.

Further Solution Notes by Demi Guo:

It’s easy to come up with a similar solution to the original solution with lower complexity. Assume we call it a ‘direct path’ between two hub x & y if there’s no hub other than x and y. It is easy to observe that a ‘direct path’ between x and y can be either edge(x,y) or edge(x,z) + edge(z,y) (where z is not a hub).

STEP1: Calculate the direct path between two hubs

Find a neighbor of a
hub A. Assume it’s farm B. If it’s a hub, then we just update the
direct path between A & B. Else, we find a neighbor of farm B. Assume
it’s C. If C is a hub then we update the direct path between A & C
using value e(A,B)+e(B,C). The complexity of this process is O(MK)
since the total # of the neighbors of a farm which is not a hub is no
more than K.

STEP2: Calculate the shortest distance between any two hubs using
the minimum ‘direct path’.

It’s a straight shortest path
problem. The complexity is O(K^3) if we use Floyd-warshall. If we use
Dijkstra, it can be reduced to either O(K log K) or O(K^{2}).

STEP3: Calculate the shortest distance between an arbitrary farm A
a hub B using the similar idea.

It is always minimum{ (A,C) + (C,B) }
where hub C is a neighbor of A. Hence it’s efficient if we find a
neighbor of A , and update the shortest distance between A and hub b.
The complexity is also O(MK).

STEP4: Calculate the shortest distance between farm A and farm B.

One way to do this is to use the idea in Fatih’s solution. We pre-calculate the shortest distance from farm A to hub C as well as the shortest distance from hub C to farm B using the approach above.

The complexity in total is O(K^3) if we use Floyd-Warshall in PART2. The complexity in total is O(MK) if we use Dijkstra in PART2.

Following is my solution written in C++. (Note that I didn’t pre-calculate the shortest distance from an arbitrary farm to a hub. Instead, I calculate it while asking the queries. It will increase the complexity to O(QK).)

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxk = 205; const int maxn = 21005; const int maxm = 21005; const ll inf = 1ll<<55; int n, m, k, q, cnt, tot; int hub[maxk], is[maxn], V[maxm], N[maxm], F[maxn]; ll C[maxm], e[maxk][maxk], d[maxk][maxn]; void add(int a,int b,ll c){ V[++tot] = b, C[tot] = c, N[tot] = F[a], F[a] = tot; } void dw(ll &x, ll y){ if (y < x) x = y; } int main(){ freopen("vacationgold.in","r",stdin); freopen("vacationgold.out","w",stdout); char ch; int a,b,c,i,j,z; ll v; #define read(x){\ ch = getchar(), x = 0;\ while (ch < '0' || ch > '9') ch = getchar();\ while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();\ } tot = 0; memset(N,0,sizeof(N)); memset(F,0,sizeof(F)); read(n);read(m);read(k);read(q); for (i = 0; i < m; i ++){ read(a); read(b); read(v); -- a, -- b, add(a,b,v); } memset(is,-1,sizeof(is)); for (i = 0; i < k; i ++){ read(hub[i]); is[--hub[i]] = i; } //STEP1 for (i = 0; i < k; i ++) for (j = 0; j < k; j ++) e[i][j] = inf; for (i = 0; i < k; i ++){ a = hub[i]; for (int p1 = F[a]; p1 > 0; p1 = N[p1]){ //case 1 if (is[b = V[p1]] >= 0){ dw(e[i][is[b]], C[p1]); continue; } //case 2 for (int p2 = F[b]; p2 > 0; p2 = N[p2]) if (is[c = V[p2]] >= 0 && i != is[c]) dw(e[i][is[c]], C[p1] + C[p2]); } } //STEP2 for (i = 0; i < k; i ++) e[i][i] = 0; for (z = 0; z < k; z ++) for (i = 0; i < k; i ++) for (j = 0; j < k; j ++) if (i != j && i != z && j != z) dw(e[i][j], e[i][z] + e[z][j]); //STEP3 for (i = 0; i < k; i ++) for (j = 0; j < n; j ++) d[i][j] = inf; for (i = 0; i < k; i ++) for (j = 0; j < k; j ++) d[i][hub[j]] = e[i][j]; for (i = 0; i < k; i ++){ for (int p = F[a = hub[i]]; p > 0; p = N[p]) for (j = 0; j < k; j ++){ dw(d[j][b = V[p]], e[j][i] + C[p]); } } //STEP4 ll tmp, res = 0; cnt = 0; while (q --){ read(a); read(b); -- a, -- b; if (is[a] >= 0) tmp = d[is[a]][b]; else{ tmp = inf; for (int p = F[a]; p > 0; p = N[p]) if (is[c = V[p]] >= 0) dw(tmp, C[p] + d[is[c]][b]); } if (tmp < inf) cnt ++, res += tmp; } printf("%d\n",cnt); printf("%lld\n",res); return 0; }