結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2017-12-04 22:10:00 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 2,237 bytes |
コンパイル時間 | 1,482 ms |
コンパイル使用メモリ | 174,972 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:34:02 |
合計ジャッジ時間 | 2,531 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include "bits/stdc++.h" #define REP(i,n) for(ll i=0;i<ll(n);++i) #define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i) #define FOR(i,m,n) for(ll i=m;i<ll(n);++i) #define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i) #define ALL(v) (v).begin(),(v).end() #define UNIQUE(v) v.erase(unique(ALL(v)),v.end()); #define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; } #define INF 1000000001ll #define MOD 1000000007ll #define EPS 1e-9 const int dx[8] = { 1,1,0,-1,-1,-1,0,1 }; const int dy[8] = { 0,1,1,1,0,-1,-1,-1 }; using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef pair<int, int> pii; typedef pair<ll, ll> pll; ll max(ll a, int b) { return max(a, ll(b)); } ll max(int a, ll b) { return max(ll(a), b); } ll min(ll a, int b) { return min(a, ll(b)); } ll min(int a, ll b) { return min(ll(a), b); } ///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)/// struct Edge { int from; int to; int cost; int weight; }; typedef vector<Edge> Edges; typedef vector<Edges> Graph; int n, c, v; vvl dijkstra(const Graph &g, int src) { vvl d(g.size(), vl(c+1,INF*INF)); d[src][c] = 0; priority_queue<pair<pii,int>, vector<pair<pii, int>>, greater<pair<pii, int>>> q; q.push({ {0,c} ,src }); while (!q.empty()) { auto p = q.top(); q.pop(); ll v = p.second, co = p.first.second; if (p.first.first > d[v][co]) continue; for (int i = 0; i < g[v].size(); ++i) { Edge e = g[v][i]; if (e.cost > co)continue; if (d[e.to][co-e.cost] > d[v][co] + e.weight) { d[e.to][co-e.cost] = d[v][co] + e.weight; q.push({ {d[e.to][co - e.cost],co - e.cost }, e.to}); //prev[e.to] = v; } } } return d; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n >> c >> v; vi s(v), t(v), y(v), m(v); REP(i, v)cin >> s[i]; REP(i, v)cin >> t[i]; REP(i, v)cin >> y[i]; REP(i, v)cin >> m[i]; Graph g(n); REP(i, v) { s[i]--; t[i]--; g[s[i]].push_back(Edge{ s[i],t[i],y[i],m[i] }); } auto d = dijkstra(g, 0); ll ans = INF*INF; REP(i, c + 1) { ans = min(ans, d[n - 1][i]); } if (ans == INF*INF)cout << -1 << endl; else cout << ans << endl; }