fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. #define ll long long
  6. #define pb push_back
  7. #define ff first
  8. #define ss second
  9.  
  10. vector<vector<pair<ll,ll>>> adj;
  11. vector<bool> vis;
  12. ll dp[100005][2];
  13. ll n,m;
  14.  
  15. ll dfs(ll node,bool flag){
  16.  
  17.     if(node==n-1) return 0;
  18.  
  19.     if(dp[node][flag]!=-1) return dp[node][flag];
  20.  
  21.     vis[node]=true;
  22.     ll k=1e18;
  23.  
  24.     for(auto e:adj[node]){
  25.  
  26.         int child=e.first;
  27.         ll weight=e.ss;
  28.  
  29.         if(!vis[child]){
  30.             if(flag){
  31.                 k=min(k,weight/2+dfs(child,false));
  32.  
  33.             }
  34.             k=min(k,weight+dfs(child,flag));
  35.  
  36.         }
  37.  
  38.     }
  39.  
  40.     vis[node]=false;
  41.  
  42.     return dp[node][flag]=k;
  43.  
  44.  
  45. }
  46.  
  47.  
  48. int main(){
  49.  
  50.     cin>>n>>m;
  51.  
  52.     adj.resize(n);
  53.     vis.resize(n);
  54.  
  55.     memset(dp,-1,sizeof dp);
  56.  
  57.  
  58.     for(ll i=0;i<m;i++){
  59.         ll u,v,w; cin>>u>>v>>w;
  60.         adj[u-1].pb({v-1,w});
  61.     }
  62.  
  63.     cout<<dfs(0,true);
  64.  
  65.     return 0;
  66.  
  67. }
Runtime error #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3FXQ4R
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!