結果
問題 |
No.1 道のショートカット
|
ユーザー |
![]() |
提出日時 | 2018-03-28 16:28:22 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,005 bytes |
コンパイル時間 | 1,561 ms |
コンパイル使用メモリ | 170,588 KB |
実行使用メモリ | 813,784 KB |
最終ジャッジ日時 | 2024-07-08 05:00:10 |
合計ジャッジ時間 | 6,354 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 13 WA * 5 RE * 1 MLE * 1 -- * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct road { int s, t, y, m; bool operator<(const road& right) const { return s<right.s; } }; int main() { int n, c, v; cin >> n >> c >> v; vector<road> r(v); for (int i = 0;i < v;i++) { cin >> r[i].s; } for (int i = 0;i < v;i++) { cin >> r[i].t; } for (int i = 0;i < v;i++) { cin >> r[i].y; } for (int i = 0;i < v;i++) { cin >> r[i].m; } sort(r.begin(), r.end()); int mi = 1000000000; vector<queue<pair<int,int>>> q(v+1); int j = 0; q[1].push(pair<int,int>{ 0,0 }); for (int i = 1;i < n;i++) { while (!q[i].empty()) { pair<int,int> qf = q[i].front();q[i].pop(); for (int k = j;k < v&&r[k].s==i;k++) { if (qf.first + r[i].y <= c) { if (r[k].t == n) { mi = min(mi, qf.second + r[k].m); } else { q[r[k].t].push(pair<int,int>{qf.first + r[k].y,qf.second + r[k].m }); } } } } for (;j < v&&r[j].s == i;j++); } cout << ((mi == 1000000000) ? -1 : mi) << endl; return 0; }