➤ Problem Link : SERVICE
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
int dp[1001][201][201];
while(t--)
{
int n,l,ans;
cin>>l>>n;
int arr[l+1][l+1];
int req[n+1];
for(int i=1;i<=l;i++)
{
for(int j=1;j<=l;j++)
cin>>arr[i][j];
}
for(int i=1;i<=n;i++)
cin>>req[i];
memset(dp,0,sizeof(dp));
for(int i=n;i>1;i--)
{
for(int j=1;j<=l;j++)
{
for(int k=1;k<=l;k++)
{
if(i==n)
{
if(req[i-1]==req[i] || j==req[i] || k==req[i])
dp[i][j][k]=0;
else
dp[i][j][k]=min(arr[req[i-1]][req[i]],min(arr[j][req[i]],arr[k][req[i]]));
}
else
{
if(req[i-1]==req[i])
dp[i][j][k]=dp[i+1][j][k];
else if(j==req[i])
dp[i][j][k]=dp[i+1][req[i-1]][k];
else if(k==req[i])
dp[i][j][k]=dp[i+1][j][req[i-1]];
else
{
dp[i][j][k]=min(arr[req[i-1]][req[i]]+dp[i+1][j][k],min(arr[j][req[i]]+dp[i+1][req[i-1]][k],arr[k][req[i]]+dp[i+1][req[i-1]][j]));
}
}
}
}
}
if(req[1]==1)
ans=dp[2][2][3];
else if(req[1]==2)
ans=dp[2][1][3];
else if(req[1]==3)
ans=dp[2][1][2];
else
ans=min(arr[1][req[1]]+dp[2][2][3],min(arr[2][req[1]]+dp[2][1][3],arr[3][req[1]]+dp[2][1][2]));
cout<<ans<<endl;
// cout<<dp[2][2][3]<<" "<<dp[3][4][3]<<" "<<dp[4][2][3]<<" "<<dp[8][4][5]<<dp[9][4][5]<<dp[9][3][4];
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.