結果

問題 No.614 壊れたキャンパス
ユーザー 0x19f0x19f
提出日時 2017-12-14 01:01:41
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 619 ms / 2,000 ms
コード長 1,599 bytes
コンパイル時間 1,714 ms
コンパイル使用メモリ 173,064 KB
実行使用メモリ 62,828 KB
最終ジャッジ日時 2024-12-14 10:40:56
合計ジャッジ時間 8,615 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
20,748 KB
testcase_01 AC 8 ms
21,288 KB
testcase_02 AC 7 ms
17,968 KB
testcase_03 AC 7 ms
17,880 KB
testcase_04 AC 8 ms
20,732 KB
testcase_05 AC 7 ms
20,824 KB
testcase_06 AC 8 ms
21,040 KB
testcase_07 AC 7 ms
17,764 KB
testcase_08 AC 526 ms
59,500 KB
testcase_09 AC 545 ms
58,216 KB
testcase_10 AC 502 ms
56,304 KB
testcase_11 AC 568 ms
60,636 KB
testcase_12 AC 619 ms
60,188 KB
testcase_13 AC 578 ms
62,256 KB
testcase_14 AC 547 ms
61,120 KB
testcase_15 AC 430 ms
56,812 KB
testcase_16 AC 479 ms
59,212 KB
testcase_17 AC 344 ms
50,736 KB
testcase_18 AC 326 ms
62,828 KB
testcase_19 AC 264 ms
55,456 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
#define INF (1LL << 60)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

ll N, M, K, S, T, A[200000], B[200000], C[200000];
vector<pll> V, E[600000];

int main(void) {
  cin >> N >> M >> K >> S >> T;
  S--; T--;
  REP(i, 0, M) {
    cin >> A[i] >> B[i] >> C[i];
    A[i]--; B[i]--; C[i]--;
    V.push_back(pll(A[i], B[i]));
    V.push_back(pll(A[i] + 1, C[i]));
  }
  V.push_back(pll(0, S));
  V.push_back(pll(N - 1, T));

  sort(V.begin(), V.end());
  V.erase(unique(V.begin(), V.end()), V.end());

  REP(i, 0, V.size() - 1) {
    if(V[i].first == V[i + 1].first) {
      ll d = abs(V[i].second - V[i + 1].second);
      E[i].push_back(pll(i + 1, d));
      E[i + 1].push_back(pll(i, d));
    }
  }
  REP(i, 0, M) {
    ll b = lower_bound(V.begin(), V.end(), pll(A[i], B[i])) - V.begin();
    ll c = lower_bound(V.begin(), V.end(), pll(A[i] + 1, C[i])) - V.begin();
    E[b].push_back(pll(c, 0));
  }

  ll s = lower_bound(V.begin(), V.end(), pll(0, S)) - V.begin();
  ll g = lower_bound(V.begin(), V.end(), pll(N - 1, T)) - V.begin();

  priority_queue<pll, vector<pll>, greater<pll> > q;
  q.push(pll(0, s));
  vector<ll> dp(V.size(), INF);
  while(q.size()) {
    ll d = q.top().first;
    ll v = q.top().second;
    q.pop();

    if(dp[v] <= d) continue;
    dp[v] = d;

    if(v == g) break;

    REP(i, 0, E[v].size()) {
      ll nd = d + E[v][i].second;
      ll nv = E[v][i].first;
      if(dp[nv] > d) q.push(pll(nd, nv));
    }
  }
  cout << (dp[g] != INF ? dp[g] : -1) << endl;
}
0