Viagem.cpp

#include<bits/stdc++.h>
using namespace std;
const int infinito = 1e9+10;
const int MAXN = 10010;
const int MAXVAL = 210;

int n, m, v, dist[MAXN][MAXVAL], marcado[MAXN][MAXVAL];
vector<pair<pair<int,int>,int>> viz[MAXN][MAXVAL];

int main() {
    cin >> v >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a,b,t,p;
        cin >> a >> b >> t >> p;
        for(int val = 0; val <= v-p; val++) {
            viz[a][val].push_back({{b,val+p},t});
            viz[b][val].push_back({{a,val+p},t});
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int val = 0; val <= v; val++) {
            dist[i][val] = infinito;
        }
    }

    int x,y; 
    cin >> x >> y;
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
    dist[x][0] = 0;
    pq.push({0,{x,0}});

    while(pq.size()) {
        int a = pq.top().second.first;
        int val = pq.top().second.second;
        pq.pop();

        if(marcado[a][val]) continue;
        marcado[a][val] = 1;
        for(auto X : viz[a][val]) {
            int b = X.first.first;
            int valb = X.first.second;
            int t = X.second;
            if(dist[b][valb] > dist[a][val]+t) {
                dist[b][valb] = dist[a][val]+t;
                pq.push({dist[b][valb],{b,valb}});
            }
        }
    }

    int ans = infinito;
    for(int val = 0; val <= v; val++) {
        ans = min(ans, dist[y][val]);
    }

    if(ans == infinito) {
        cout << -1 << endl;
    }
    else {
        cout << ans << endl;
    }
}