Advertisement
YEZAELP

CUBE-043: Kill Time

Jul 7th, 2020
81
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF=1e9;
  5. using pii = pair<int,pair<int,int>>;
  6. vector <pii> g[301];
  7. vector < vector<int> > dp( 301 , vector<int> (2001,-INF) );
  8. int t,k;//end
  9.  
  10. int dfs(int u,int time){
  11.     if(time == k && u != t) return -INF;
  12.     if(time > k) return -INF;
  13.     if(u == t) return 0;
  14.     if(dp[u][time] != -INF) return dp[u][time];
  15.     for(auto vcw:g[u]){
  16.         int v,c,w;
  17.         v = vcw.first;
  18.         c = vcw.second.first;
  19.         w = vcw.second.second;
  20.         dp[u][time] = max( dp[u][time] , c+dfs(v,time+w) );
  21.     }
  22.     return dp[u][time];
  23. }
  24.  
  25. int main(){
  26.  
  27.     int n,m,s;
  28.     scanf("%d %d %d ",&n,&m,&k);
  29.     scanf("%d %d",&s,&t);
  30.     for(int i=1;i<=m;i++){
  31.         int u,v,w,c;
  32.         scanf("%d %d %lld %d",&u,&v,&c,&w);
  33.         g[u].push_back({ v,{c,w} });
  34.         g[v].push_back({ u,{c,w} });
  35.     }
  36.  
  37.     int ans=dfs(s,0);
  38.     if(ans<0) printf("Impossible");
  39.     else printf("%d",ans);
  40.  
  41.     return 0;
  42. }
  43. /*
  44. 7 7 6
  45. 1 7
  46. 1 7 10 6
  47. 2 3 2 1
  48. 1 2 2 1
  49. 3 4 2 1
  50. 4 5 2 1
  51. 5 6 2 1
  52. 6 7 2 1
  53. */
Advertisement
RAW Paste Data Copied
Advertisement