結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2015-12-13 03:33:53 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 15 ms / 5,000 ms |
コード長 | 1,704 bytes |
コンパイル時間 | 769 ms |
コンパイル使用メモリ | 100,628 KB |
実行使用メモリ | 9,216 KB |
最終ジャッジ日時 | 2024-07-20 16:18:42 |
合計ジャッジ時間 | 1,865 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <vector> #include <array> #include <algorithm> #include <string> #include <map> #include <queue> #include <iomanip> #include <numeric> #include <memory> #include <limits.h> #include <set> #include <cassert> #include <cmath> #include <bitset> #include <functional> using namespace std; typedef long long ll; #define REP(i,n) for(ll i=0; i<(n); ++i) #define TEN(x) ((ll)1e##x) #define ALL(v) (v).begin(), (v).end() #define INF_DIST 10000 using Distance = ll; using Id = ll; struct edge{Id to; Distance cost;}; using Graph = vector<vector<edge>>; vector<Distance> dijkstra(Id s, const Graph & g){ vector<Distance> d(g.size(), INF_DIST); d[s] = 0; using P = pair<Distance, Id>; priority_queue<P, vector<P>, greater<P>> que; que.push(P(0, s)); while(!que.empty()){ auto p = que.top(); que.pop(); Id v = p.second; if(d[v] < p.first) continue; for (auto e : g[v]) if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } return d; } Id calc_id(ll i, ll c, ll n) { return i + n * c; } int main(){ ll n, c, v; cin >> n >> c >> v; vector<ll> s(v); vector<ll> t(v); vector<ll> y(v); vector<ll> m(v); for (auto&i : s) cin >> i; for (auto&i : t) cin >> i; for (auto&i : y) cin >> i; for (auto&i : m) cin >> i; for (auto&i : s) --i; for (auto&i : t) --i; ll n_extended = calc_id(n,c,n); Graph g(n_extended); REP(i, v) REP(j, c + 1) if(j >= y[i]) { g[calc_id(s[i], j, n)].push_back({ calc_id(t[i], j - y[i], n), m[i] }); } auto d = dijkstra(calc_id(0, c, n), g); ll min_d = INF_DIST; REP(i, c+1) min_d = min(min_d, d[calc_id(n - 1, i, n)]); cout << (min_d != INF_DIST ? min_d : -1) << endl; return 0; }