結果

問題 No.614 壊れたキャンパス
ユーザー 0x19f0x19f
提出日時 2017-12-14 00:59:41
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 1,599 bytes
コンパイル時間 1,751 ms
コンパイル使用メモリ 171,416 KB
実行使用メモリ 29,788 KB
最終ジャッジ日時 2024-05-08 08:14:41
合計ジャッジ時間 10,212 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
8,320 KB
testcase_01 AC 5 ms
8,064 KB
testcase_02 AC 5 ms
8,192 KB
testcase_03 AC 5 ms
8,192 KB
testcase_04 AC 4 ms
8,192 KB
testcase_05 AC 5 ms
8,192 KB
testcase_06 AC 5 ms
8,064 KB
testcase_07 AC 4 ms
8,064 KB
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
権限があれば一括ダウンロードができます

ソースコード

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[200000];

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