fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define killua ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
  5. #define int long long
  6. #define ll long long
  7. ll mod = 1e9 + 9;
  8. #define int long long
  9. ll n,m;
  10. int operation_less[201][201];
  11. vector<ll>del(201,1e18);
  12. int dp[201][201];
  13. vector<ll>v(201);
  14. int solve(ll idx,ll last)
  15. {
  16.     if(idx==n)
  17.         return 0;
  18.     ll &ret=dp[idx][last];
  19.     if(ret!=-1)return ret;
  20.     ret=1e18;
  21.     for(int i=0;i<=200;i++)
  22.     {
  23.         if(operation_less[v[idx]][i]!=1e18)
  24.         {
  25.             if(i>=last)
  26.             ret=min(ret, solve(idx+1,i)+operation_less[v[idx]][i]);
  27.             ret=min(ret, solve(idx+1,last)+operation_less[v[idx]][i]+del[i]);
  28.         }
  29.     }
  30.     if(del[v[idx]]!=1e18)
  31.         ret=min(ret, solve(idx+1,last)+del[v[idx]]);
  32.     if(v[idx]>=last)ret=min(ret, solve(idx+1,v[idx]));
  33.     return ret;
  34. }
  35. signed main() {
  36.     killua;
  37.  
  38.     cin>>n>>m;
  39.  
  40.     for(int i=0;i<n;i++)
  41.         cin>>v[i];
  42.     for(int i=0;i<=200;i++)
  43.     {
  44.         for(int j=0;j<=200;j++)
  45.             operation_less[i][j]=1e18;
  46.     }
  47.  
  48.     //vector<vector<pair<ll,ll>>>operation_less(n);
  49.     for(int i=0;i<m;i++)
  50.     {
  51.         ll op;
  52.         cin>>op;
  53.         if(op==1)
  54.         {
  55.             ll x,y,c;
  56.             cin>>x>>y>>c;
  57.             operation_less[x][y]=min(operation_less[x][y],c);
  58.         }
  59.         else
  60.         {
  61.             ll x,c;
  62.             cin>>x>>c;
  63.             del[x]=min(c,del[x]);
  64.         }
  65.  
  66.     }
  67.  
  68.     for(int i = 0 ; i <= 200 ;i++)operation_less[i][i] = 0;
  69.  
  70.  
  71.     for(int i = 0 ; i <= 200 ; i++)
  72.     {
  73.         for(int j = 0 ; j <= 200;j++)
  74.         {
  75.             for(int k = 0 ; k <= 200; k++)
  76.             {
  77.                 operation_less[j][k] = min(operation_less[j][k] , operation_less[j][i] + operation_less[i][k]);
  78.             }
  79.         }
  80.     }
  81.  
  82.     memset(dp,-1,sizeof dp);
  83.     if(solve(0,0)>=1e18)
  84.         cout<<-1<<endl;
  85.     else
  86.         cout<<solve(0,0)<<endl;
  87.  
  88. }
Success #stdin #stdout 0.02s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/s3gtng
language:
C++14 (gcc 8.3)
created:
44 days 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!