結果
問題 | No.1 道のショートカット |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
#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; }