Official

E - Souvenir Editorial by en_translator

First, we ignore the souvenirs and determine if he can travel from city \(S\) to city \(T\). If it is possible, we find the minimum number of direct flights required. This can be solved as a shortest path problem on a graph whose vertices are the cities and edges are the direct flights with weight \(1\). We then want to improve this to find the maximum sum of souvenirs that he can buy in a shortest path.

Currently, the values of the souvenirs are associated to the vertices and cannot be solved as a shortest path problem. However, a shortest path has a property that it doesn’t visit the same city twice. Thus, we can consider Takahashi’s move from city \(S\) to city \(T\) as follows.

  • When he starts, he buys a souvenir of value \(A_S\).
  • Then, he repeats the following action until he reaches city \(T\): move from city \(U_i\) to city \(V_i\) and buy a souvenir of value \(A_{V_i}\).

For fixed \(S\) and \(T\), the first step is equivalent for every path, so it is sufficient to find the shortest distance and the maximum sum of values in a shortest path. \(\cdots (*)\)

In an ordinary shortest path problem, we keep updating \(d(X,Y)\) that denotes the (preliminary) shortest distance from city \(X\) to city \(Y\); this time, we can keep updating \((d(X,Y), val(X,Y))\) that denotes ((preliminary) shortest distance from city \(X\) and city \(Y\), (preliminary) maximum sum of values of souvenir in a path that achieves the (preliminary) shortest distance).

Then, edge \(i\) should be updated when

  • \(d(X,U_i)+1<d(X,V_i)\)

or

  • \(d(X,U_i)+1=d(X,V_i)\) and \(val(X,U_i)+A_{V_i}>val(X,V_i)\)

by \((d(X,V_i),val(X,V_i))\leftarrow (d(X,U_i)+1,val(X,U_i)+A_{V_i})\). (Flipping the sign of \(val(X,Y)\), we can also choose the lexicographically smaller one.)

Therefore, we can find the answer between all pairs of cities with Warshall-Floyd algorithm with such updates. The complexity is \(O(N^3)\), which is fast enough.
Since the first criteria \(d(X,Y)\) always increases by passing through an edge, there is no so-called negative cycle. Thus, it can also be solved with Dijkstra’s algorithm etc. in a total of \(O(N(M+N\log N))\) or \(O(NM\log N)\) time, which is still realistic.

Thus, the problem has been solved.

Alternative solution using $\epsilon$ to handle $(*)$ Let $\epsilon$ be a sufficiently small positive number, and consider a shortest path problem on a graph where edge $i$ goes from vertex $U_i$ to vertex $V_i$ with cost $1-\epsilon A_{V_i}$. If the shortest distance from $S$ to $T$ is $X-Y\epsilon$, the shortest distance turns out to be $X$, and the sum of values of souvenir to $Y$. In practice, the errors are unavoidable so it is safer to use the lexicographical order.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n;
	long long a[300];
	string s;
	int d[300][300];
    long long val[300][300];

	cin >>n;
	for(int i=0;i<n;i++)cin>>a[i];

	for(int i=0;i<n;i++)for(int j=0;j<n;j++)d[i][j]=n,val[i][j]=0;
	for(int i=0;i<n;i++)d[i][i]=0,val[i][i]=0;
	for(int i=0;i<n;i++){
		cin >> s;
		for(int j=0;j<n;j++){
			if(s[j]=='Y')d[i][j]=1,val[i][j]=a[j];
		}
	}

	for(int j=0;j<n;j++){
		for(int i=0;i<n;i++){
			for(int k=0;k<n;k++){
				if((d[i][j]+d[j][k])<d[i][k]){
					d[i][k]=d[i][j]+d[j][k];
					val[i][k]=val[i][j]+val[j][k];
				}
				else if(((d[i][j]+d[j][k])==d[i][k])&&((val[i][j]+val[j][k])>val[i][k])){
					val[i][k]=val[i][j]+val[j][k];
				}
			}
		}
	}

	int q,u,v;
	cin >> q;
	for(int i=0;i<q;i++){
		cin >> u >> v;
		if(d[u-1][v-1]==n)cout<<"Impossible\n";
		else cout<<d[u-1][v-1]<<" "<<(val[u-1][v-1]+a[u-1])<<"\n";
	}
	return 0;
}

posted:
last update: