CUBE-043: Kill Time

#include <bits/stdc++.h>
using namespace std;

const int INF=1e9;
using pii = pair<int,pair<int,int>>;
vector <pii> g[301];
vector < vector<int> > dp( 301 , vector<int> (2001,-INF) );
int t,k;//end

int dfs(int u,int time){
    if(time == k && u != t) return -INF;
    if(time > k) return -INF;
    if(u == t) return 0;
    if(dp[u][time] != -INF) return dp[u][time];
    for(auto vcw:g[u]){
        int v,c,w;
        v = vcw.first;
        c = vcw.second.first;
        w = vcw.second.second;
        dp[u][time] = max( dp[u][time] , c+dfs(v,time+w) );
    }
    return dp[u][time];
}

int main(){

    int n,m,s;
    scanf("%d %d %d ",&n,&m,&k);
    scanf("%d %d",&s,&t);
    for(int i=1;i<=m;i++){
        int u,v,w,c;
        scanf("%d %d %lld %d",&u,&v,&c,&w);
        g[u].push_back({ v,{c,w} });
        g[v].push_back({ u,{c,w} });
    }

    int ans=dfs(s,0);
    if(ans<0) printf("Impossible");
    else printf("%d",ans);

    return 0;
}
/*
7 7 6
1 7
1 7 10 6
2 3 2 1
1 2 2 1
3 4 2 1
4 5 2 1
5 6 2 1
6 7 2 1
*/