fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef int ll;
  4. typedef pair<ll,ll> pll;
  5. #define fi first
  6. #define sc second
  7. #define pb push_back
  8. #define mp make_pair 
  9. #define FOR(i,a,b) for(ll i=a;i<=b;i++)
  10. #define FORD(i,b,a) for(ll i=b;i>=a;i--)
  11. const ll N = 201;
  12. const ll M = 1001;
  13. const ll oo = 1e9+5;
  14. ll n,m,k;
  15. ll a[N][N];
  16. ll q[M];
  17. ll f[N][N][M];
  18. int main(){
  19.     ios_base::sync_with_stdio(0);
  20.     cin.tie(0);cout.tie(0);
  21.     // freopen("serv.inp","r",stdin);
  22.     // freopen("serv.out","w",stdout);
  23.     cin>>n>>m;
  24.     FOR(i,1,n)
  25.     FOR(j,1,n) cin>>a[i][j];
  26.  
  27.     FOR(i,1,m)
  28.         cin>>q[i];
  29.     q[0] = 3;
  30.     ll a1, a2, a3;
  31.     FORD(k,m,1)
  32.     FOR(i,1,n)
  33.     FOR(j,i + 1,n){
  34.         if (f[i][j][k] != 0) continue;
  35.         if (i == q[k - 1] || j == q[k - 1]) continue;
  36.         a1 = a2 = a3 = oo;
  37.         if (i != q[k] && j != q[k] ) a1 = f[i][j][k+1] + a[q[k-1]][q[k]];
  38.         if (i != q[k] && q[k-1] != q[k] && i != q[k-1])
  39.             a2 = f[min(i, q[k - 1])][max(i, q[k-1])][k+1]  + a[j][q[k]];
  40.  
  41.         if (j != q[k] && q[k-1] != q[k] && j != q[k-1]) 
  42.             a3 = f[min(j, q[k - 1])][max(j, q[k-1])][k+1]  + a[i][q[k]];
  43.         f[i][j][k] = min( {a1, a2, a3} );
  44.     }
  45.     cout<<f[1][2][1];
  46. }
  47.  
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fQGHJz
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!