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²).

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;
}