結果

問題 No.614 壊れたキャンパス
ユーザー legosukelegosuke
提出日時 2017-12-14 16:39:10
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 1,685 bytes
コンパイル時間 1,732 ms
コンパイル使用メモリ 174,500 KB
実行使用メモリ 101,524 KB
最終ジャッジ日時 2023-08-21 04:33:54
合計ジャッジ時間 19,652 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
12,668 KB
testcase_01 AC 6 ms
12,664 KB
testcase_02 AC 6 ms
12,752 KB
testcase_03 AC 6 ms
12,680 KB
testcase_04 AC 6 ms
12,680 KB
testcase_05 AC 6 ms
12,668 KB
testcase_06 AC 6 ms
12,712 KB
testcase_07 AC 6 ms
12,688 KB
testcase_08 AC 1,422 ms
99,396 KB
testcase_09 AC 1,880 ms
99,748 KB
testcase_10 RE -
testcase_11 AC 1,509 ms
101,160 KB
testcase_12 AC 1,585 ms
101,040 KB
testcase_13 AC 1,543 ms
101,524 KB
testcase_14 AC 1,461 ms
100,636 KB
testcase_15 RE -
testcase_16 AC 1,332 ms
98,756 KB
testcase_17 AC 1,316 ms
90,772 KB
testcase_18 AC 1,101 ms
85,880 KB
testcase_19 AC 1,324 ms
87,616 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, pii> lpi;

struct edge {
  pii to;
  ll cost;
  edge() {}
  edge(pii t, ll c) : to(t), cost(c) {}
};

int n, m, k, s, t;
int a, b, c;

vector<int> v[400010];
map< pii, vector<edge> > G;
map<pii, ll> d;

template<typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

void dijkstra(pii s) {
  priority_queue< lpi, vector<lpi>, greater<lpi> > que;
  que.push(lpi(0LL, s));
  d[s] = 0LL;
  while (!que.empty()) {
    lpi p = que.top(); que.pop();
    pii v = p.second;
    if (d[v] < p.first) continue;
    for (int i = 0; i < G[v].size(); i++) {
      edge e = G[v][i];
      if (d[e.to] <= d[v] + e.cost) continue;
      d[e.to] = d[v] + e.cost;
      que.push(lpi(d[e.to], e.to));
    }
  }
}

int main(void) {
  cin >> n >> m >> k >> s >> t;
  for (int i = 0; i < m; i++) {
    cin >> a >> b >> c;
    G[pii(a, b)].push_back(edge(pii(a + 1, c), 0));
    v[a].push_back(b);
    v[a + 1].push_back(c);
  }
  v[1].push_back(s);
  v[n].push_back(t);
  d[pii(1, s)] = 1LL << 60;
  d[pii(n, t)] = 1LL << 60;
  
  for (int i = 1; i <= n; i++) {
    sort(v[i].begin(), v[i].end());
    for (int j = 0; j < v[i].size() - 1; j++) {
      G[pii(i, v[i][j])].push_back(edge(pii(i, v[i][j + 1]), v[i][j + 1] - v[i][j]));
      G[pii(i, v[i][j + 1])].push_back(edge(pii(i, v[i][j]), v[i][j + 1] - v[i][j]));
      d[pii(i, v[i][j])] = d[pii(i, v[i][j + 1])] = 1LL << 60;
    }
  }
  dijkstra(pii(1, s));

  ll ans = d[pii(n, t)];
  cout << (ans == 1LL << 60 ? -1 : ans) << endl;

  return 0;
}
0