[POJ] 1724 ROADS.cpp

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define INF 99999999

struct Point_type {
    vector<int> D;    // next point index
    vector<int> L;    // length
    vector<int> T;    // toll
}S[101];
int Dis[101][10001]; //Dis[i][j] 為從起點1到點i花費j元的最短距離

int main()
{
    int K, N, R;
    scanf("%d %d %d", &K, &N, &R);
    
    // Initialize Dis[][]
    for (int i = 1; i <= N; ++i)
        for (int j = 0; j <= K; ++j)
            Dis[i][j] = INF;
    for (int i = 0; i <= K; ++i)
        Dis[1][i] = 0;

    // Input
    int s, d, l, t;
    for (int i = 0; i < R; ++i) {
        scanf("%d %d %d %d", &s, &d, &l, &t);
        S[s].D.push_back(d);
        S[s].L.push_back(l);
        S[s].T.push_back(t);
    }

    // SPFA
    queue<int> Q;
    bool inQueue[101] = {0};
    Q.push(1);
    inQueue[1] = true;

    while (!Q.empty()) {
        int now = Q.front();
        inQueue[now] = false;
        Q.pop();

        for (int i = 0; i < S[now].D.size(); ++i) {
            int nxt = (S[now].D)[i];
            int L = S[now].L[i];
            int T = S[now].T[i];
            for (int j = 0; j + T <= K; ++j) {
                if (Dis[now][j] + L < Dis[nxt][j+T]) {
                    Dis[nxt][j+T] = Dis[now][j] + L;
                    if (!inQueue[nxt]) {
                        Q.push(nxt);
                        inQueue[nxt] = true;
                    }
                }
            }
        }
    }
    // Analysis
    int Shortest = INF;
    for (int i = 0; i <= K; ++i)
        if (Dis[N][i] < Shortest)
            Shortest = Dis[N][i];

    // Output
    if (Shortest == INF) puts("-1");
    else printf("%d\n", Shortest);
}