結果

問題 No.614 壊れたキャンパス
ユーザー legosukelegosuke
提出日時 2017-12-14 16:39:10
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 1,685 bytes
コンパイル時間 2,426 ms
コンパイル使用メモリ 187,144 KB
実行使用メモリ 101,632 KB
最終ジャッジ日時 2024-05-08 10:06:32
合計ジャッジ時間 19,232 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
12,672 KB
testcase_01 AC 6 ms
12,672 KB
testcase_02 AC 5 ms
12,672 KB
testcase_03 AC 4 ms
12,672 KB
testcase_04 AC 4 ms
12,800 KB
testcase_05 AC 5 ms
12,672 KB
testcase_06 AC 5 ms
12,800 KB
testcase_07 AC 5 ms
12,904 KB
testcase_08 AC 1,368 ms
99,572 KB
testcase_09 AC 1,801 ms
100,084 KB
testcase_10 RE -
testcase_11 AC 1,494 ms
101,152 KB
testcase_12 AC 1,551 ms
101,248 KB
testcase_13 AC 1,512 ms
101,632 KB
testcase_14 AC 1,399 ms
100,696 KB
testcase_15 RE -
testcase_16 AC 1,335 ms
98,780 KB
testcase_17 AC 1,302 ms
90,752 KB
testcase_18 AC 1,078 ms
84,952 KB
testcase_19 AC 1,284 ms
87,204 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