結果

問題 No.614 壊れたキャンパス
ユーザー legosuke
提出日時 2017-12-14 16:39:10
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 1,685 bytes
コンパイル時間 2,228 ms
コンパイル使用メモリ 189,220 KB
実行使用メモリ 101,592 KB
最終ジャッジ日時 2024-12-14 13:15:24
合計ジャッジ時間 19,350 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 RE * 2
権限があれば一括ダウンロードができます

ソースコード

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