結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2015-02-11 07:40:59 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 17 ms / 5,000 ms |
コード長 | 1,569 bytes |
コンパイル時間 | 1,764 ms |
コンパイル使用メモリ | 169,868 KB |
実行使用メモリ | 8,320 KB |
最終ジャッジ日時 | 2024-07-20 16:09:06 |
合計ジャッジ時間 | 2,870 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> #define REP(i,n) for(int i=0;i<(int)(n);i++) #define ALL(x) (x).begin(),(x).end() using namespace std; typedef int Weight; Weight INF = 1000000000; struct Edge{ int src, dest; Weight weight; }; typedef vector<Edge> Edges; typedef vector<Edges> Graph; typedef vector<Weight> Array; typedef vector<Array> Matrix; int N, C, V, s[2048], t[2048], y[2048], m[2048]; int getId(int i, int c) { return i * (C + 1) + c; } void add_edge(Graph &g, int src, int dest, Weight weight) { g[src].push_back((Edge){src, dest, weight}); } void dijkstra(Graph &g, Array &d, int s) { d.assign(g.size(), INF); d[s] = 0; typedef pair<Weight,int> P; priority_queue<P, vector<P>, greater<P> > que; que.push(P(0, s)); while (!que.empty()) { Weight dist = que.top().first; int v = que.top().second; que.pop(); if (d[v] < dist) continue; REP(i, g[v].size()) { Edge e = g[v][i]; if (d[e.dest] > d[v] + e.weight) { d[e.dest] = d[v] + e.weight; que.push(P(d[e.dest], e.dest)); } } } } int main() { cin >> N >> C >> 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 * (C + 1)); REP(i,N) REP(j,C) add_edge(g, getId(i, j+1), getId(i, j), 0); REP(i,V) REP(j,C+1) { int nj = j - y[i]; if (nj < 0) continue; add_edge(g, getId(s[i]-1, j), getId(t[i]-1, nj), m[i]); } Array d; dijkstra(g, d, getId(0, C)); int res = d[getId(N-1, 0)]; if (res == INF) cout << -1 << endl; else cout << res << endl; return 0; }