結果

問題 No.1 道のショートカット
コンテスト
ユーザー Nachia
提出日時 2020-09-27 11:22:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 33 ms / 5,000 ms
コード長 1,053 bytes
コンパイル時間 1,793 ms
コンパイル使用メモリ 176,284 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-20 16:51:49
合計ジャッジ時間 3,189 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

struct Edge { int v, c, d; };

int N, C, M;
int D[50][301];
vector<Edge> E[50];
const int INF = 1000000000;

int main() {
    cin >> N >> C >> M;
    {
        int Ebuf[1500][4]; rep(j, 4) rep(i, M) cin >> Ebuf[i][j];
        rep(i, M) E[Ebuf[i][0] - 1].push_back({ Ebuf[i][1] - 1,Ebuf[i][2],Ebuf[i][3] });
    }

    rep(i, N) rep(j, C + 1) D[i][j] = INF;
    priority_queue<pair<int, pair<int, int>>> Q; Q.push({ 0,{0,C} });
    while (Q.size()) {
        int d = Q.top().first;
        int p = Q.top().second.first;
        int c = Q.top().second.second; Q.pop();
        if (D[p][c] != INF) continue;
        D[p][c] = -d;
        for (Edge& e : E[p]) {
            if (c < e.c) continue;
            Q.push({ d - e.d, {e.v, c - e.c} });
        }
    }

    int ans = INF;
    rep(i, C + 1) ans = min(ans, D[N - 1][i]);
    if (ans == INF) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}
0