結果

問題 No.1 道のショートカット
ユーザー asi1024asi1024
提出日時 2015-02-11 07:40:59
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 13 ms
7,040 KB
testcase_09 AC 8 ms
5,376 KB
testcase_10 AC 6 ms
5,376 KB
testcase_11 AC 7 ms
5,376 KB
testcase_12 AC 17 ms
8,320 KB
testcase_13 AC 16 ms
7,936 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 5 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 5 ms
5,376 KB
testcase_21 AC 5 ms
5,376 KB
testcase_22 AC 4 ms
5,376 KB
testcase_23 AC 10 ms
6,912 KB
testcase_24 AC 11 ms
7,552 KB
testcase_25 AC 7 ms
5,376 KB
testcase_26 AC 6 ms
5,376 KB
testcase_27 AC 11 ms
6,656 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 4 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 3 ms
5,376 KB
testcase_32 AC 10 ms
5,960 KB
testcase_33 AC 7 ms
5,376 KB
testcase_34 AC 9 ms
6,400 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 3 ms
5,376 KB
testcase_37 AC 3 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 4 ms
5,376 KB
testcase_40 AC 3 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 1 ms
5,376 KB
testcase_43 AC 3 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0