E - Sightseeing Tour Editorial by en_translator
First of all, let \(t(i,j)\) be the time required to travel from island \(i\) to island \(j\) without any constraints. (Especially, if \(i=j\) (the starting and ending islands are the same), then let \(t(i,j)=0\).)
This can be computed for all pairs of islands in a total of \(O(N^3)\) time using Warshall-Floyd algorithm.
Consider solving the \(i\)-th (\(1\leq i\leq Q\)) problem.
In this problem, the bridges connect islands
\((U_{B_{i,1}}, V_{B_{i,1}})\) , \((U_{B_{i,2}}, V_{B_{i,2}})\) , \(\ldots\), \((U_{B_{i,K_i}}, V_{B_{i,K_i}})\).
Fix the order of using those bridges (\(K_i!\) ways) and the directions (\(2^{K_i}\) ways). When the bridges are decided to be used in the order and directions of \(x_1\to y_1\), \(x_2\to y_2\), \(\ldots\), \(x_{K_i}\to y_{K_i}\), then the minimum time required to travel from island \(i\) to island \(N\) subject to the condition is
\[ \left[ t(1,x_1)+t(y_1,x_2)+t(y_2,x_3)+\cdots+t(y_{K_i-1},x_{K_i})+t(y_{K_i},N)\right] +\left[T_{B_{i,1}}+T_{B_{i,2}}+\cdots+T_{B_{i,K_i}}. \right] \]
The final answer is the minimum of this value for all order and directions.
If we precompute \(t(i,j)\), this can be found as the sum of \((2K_i+1)\) numbers, so the number of arithmetic operations here is about \((2K_i+1)\cdot (K_i!)\cdot 2^{K_i}\). Under the constraints \((K_i\leq 5)\) of this problem, the number is a total of \(11\cdot(5!)\cdot 2^5\sim 4\times 10^4\). Since there are at most \(3000\) problems, it requires a total of \(10^8\) arithmetic operations, which is fast enough.
Therefore, the problem has been solved.
If we use dynamic programming once the order is fixed, the time required to solve one question becomes about \(\sim 5K_i\cdot (K_i!)\), which enables us to solve the problem faster.
Sample code in C++:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ll long long
#define N 400
#define M (int)2e+5
#define INF (ll)1e+15
int n;
int u[M],v[M];
ll t[M];
ll d[N][N];
int k;
vector<int>a;
ll solve(void){
ll ans=INF;
ll dp[5][2];
vector<int>b;
rep(i,k)b.push_back(i);
while(true){
dp[0][0]=d[0][v[a[b[0]]]]+t[a[b[0]]];
dp[0][1]=d[0][u[a[b[0]]]]+t[a[b[0]]];
rep(i,k-1){
dp[i+1][0]=min(dp[i][0]+d[u[a[b[i]]]][v[a[b[i+1]]]],dp[i][1]+d[v[a[b[i]]]][v[a[b[i+1]]]])+t[a[b[i+1]]];
dp[i+1][1]=min(dp[i][0]+d[u[a[b[i]]]][u[a[b[i+1]]]],dp[i][1]+d[v[a[b[i]]]][u[a[b[i+1]]]])+t[a[b[i+1]]];
}
ans=min(ans,dp[k-1][0]+d[u[a[b[k-1]]]][n-1]);
ans=min(ans,dp[k-1][1]+d[v[a[b[k-1]]]][n-1]);
if(!(next_permutation(b.begin(),b.end())))break;
}
return ans;
}
int main() {
int m,q,x;
cin>>n>>m;
rep(i,n)rep(j,n){
if(i==j)d[i][j]=0;
else d[i][j]=INF;
}
rep(i,m){
cin>>u[i]>>v[i]>>t[i];
u[i]--,v[i]--;
d[u[i]][v[i]]=min(d[u[i]][v[i]],t[i]);
d[v[i]][u[i]]=min(d[v[i]][u[i]],t[i]);
}
rep(i1,n)rep(i0,n)rep(i2,n)d[i0][i2]=min(d[i0][i2],d[i0][i1]+d[i1][i2]);
cin>>q;
rep(qq,q){
cin>>k;
a.clear();
rep(kk,k){
cin>>x;
a.push_back(x-1);
}
cout<<(solve())<<endl;
}
return 0;
}
posted:
last update: