結果
問題 |
No.1 道のショートカット
|
ユーザー |
![]() |
提出日時 | 2015-08-27 12:01:50 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,464 bytes |
コンパイル時間 | 669 ms |
コンパイル使用メモリ | 79,736 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-08 04:12:10 |
合計ジャッジ時間 | 2,301 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 3 WA * 34 RE * 3 |
ソースコード
#include <iostream> #include <numeric> #include <algorithm> #include <string> #include <vector> #include <functional> #include <cmath> #include <queue> #define rep(i, a) FOR(i, 0, a) #define FOR(i, a, b) for(int i = a; i < b; ++i) typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> P; struct edge{ int to, time, cost; }; const int max = 51; const int inf = (int)1e+9; int n, c; P cost[max]; std::vector<edge> node[max]; void dijkstra(int s){ std::priority_queue<P, std::vector<P>, std::greater<P> > que; rep(i, n)cost[i].first = inf, cost[i].second = inf; cost[s].first = 0, cost[s].second = 0; que.push(P(0, s)); while (!que.empty()){ P p = que.top(); que.pop(); if (cost[p.second].first < p.second)continue; rep(i, node[p.second].size()){ edge e = node[p.second][i]; if (p.first + e.time < cost[e.to].first && cost[p.second].second + e.cost <= c){ cost[e.to].first = p.first + e.time; cost[e.to].second = cost[p.second].second + e.cost; que.push(P(cost[e.to].first, e.to)); } } } } int main(){ int v; int s[51], t[51], y[51], m[51]; std::cin >> n >> c >> v; rep(i, n)std::cin >> s[i]; rep(i, n)std::cin >> t[i]; rep(i, n)std::cin >> y[i]; rep(i, n)std::cin >> m[i]; rep(i, n){ edge a; a.to = t[i] - 1; a.cost = y[i]; a.time = m[i]; node[s[i] - 1].push_back(a); } dijkstra(0); std::cout << (cost[n - 1].first == inf ? -1 : cost[n - 1].first) << std::endl; return 0; }