結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2021-02-25 17:46:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 77 ms / 5,000 ms |
コード長 | 1,215 bytes |
コンパイル時間 | 2,074 ms |
コンパイル使用メモリ | 211,320 KB |
最終ジャッジ日時 | 2025-01-19 04:30:27 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int INF = 1<<30; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, c; cin >> n >> c >> m; vector<int> s(m), t(m), y(m), w(m); for (int i = 0; i < m; i++) cin >> s[i]; for (int i = 0; i < m; i++) cin >> t[i]; for (int i = 0; i < m; i++) cin >> y[i]; for (int i = 0; i < m; i++) cin >> w[i]; vector<vector<tuple<int, int, int> > >edges(n); for (int i = 0; i < m; i++) { edges[s[i]-1].emplace_back(t[i]-1, y[i], w[i]); } vector<vector<int> > dist(n, vector<int>(c+1, INF)); priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>> > q; dist[0][c] = 0; q.emplace(0, 0, c); while (!q.empty()) { int cost, v, r; tie(cost, v, r) = q.top(); q.pop(); if (cost > dist[v][r]) continue; for (auto &[u, money, weight]: edges[v]) { if (r >= money && cost + weight < dist[u][r - money]) { dist[u][r - money] = cost + weight; q.emplace(dist[u][r - money], u, r - money); } } } int ret = *min_element(dist[n-1].begin(), dist[n-1].end()); if (ret == INF) ret = -1; cout << ret << endl; return 0; }