結果

問題 No.614 壊れたキャンパス
ユーザー ferinferin
提出日時 2017-12-14 21:46:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,648 ms / 2,000 ms
コード長 2,149 bytes
コンパイル時間 1,895 ms
コンパイル使用メモリ 174,084 KB
実行使用メモリ 133,664 KB
最終ジャッジ日時 2023-08-21 04:47:05
合計ジャッジ時間 18,692 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
8,032 KB
testcase_01 AC 4 ms
8,044 KB
testcase_02 AC 4 ms
8,332 KB
testcase_03 AC 4 ms
8,116 KB
testcase_04 AC 4 ms
8,032 KB
testcase_05 AC 4 ms
8,340 KB
testcase_06 AC 4 ms
8,060 KB
testcase_07 AC 4 ms
8,024 KB
testcase_08 AC 1,373 ms
132,216 KB
testcase_09 AC 1,648 ms
130,616 KB
testcase_10 AC 913 ms
125,948 KB
testcase_11 AC 1,490 ms
133,328 KB
testcase_12 AC 1,551 ms
133,320 KB
testcase_13 AC 1,492 ms
133,664 KB
testcase_14 AC 1,397 ms
133,288 KB
testcase_15 AC 826 ms
127,540 KB
testcase_16 AC 1,302 ms
130,220 KB
testcase_17 AC 1,032 ms
108,060 KB
testcase_18 AC 1,086 ms
121,200 KB
testcase_19 AC 1,179 ms
117,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

map<PII, VVI> g;
VI x[200010];
map<PII, int> d;
signed main(void)
{
  int n, m, k, s, t;
  cin >> n >> m >> k >> s >> t;
  s--, t--;
  REP(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--, c--;
    // building, floor, cost
    g[{a, b}].PB((VI){a+1, c, 0});
    x[a].PB(b);
    x[a+1].PB(c);
  }
  x[0].PB(s);
  x[n-1].PB(t);
  REP(i, n) {
    sort(ALL(x[i]));
    REP(j, x[i].size()-1) {
      // x[j] -> x[j+1]
      g[{i, x[i][j]}].PB((VI){i, x[i][j+1], x[i][j+1]-x[i][j]});
      g[{i, x[i][j+1]}].PB((VI){i, x[i][j], x[i][j+1]-x[i][j]});
      d[{i, x[i][j]}] = INF;
    }
    if(x[i].size() != 0) d[{i, x[i].back()}] = INF;
  }

  priority_queue<VI, VVI, greater<VI>> que;
  que.push({0, 0, s});
  d[{0, s}] = 0;
  while(que.size()) {
    VI v = que.top(); que.pop();
    int cost = v[0], build = v[1], flr = v[2];
    // if(build == n-1 && flr == t) break;
    if(cost > d[{build, flr}]) continue;
    for(VI i: g[{build, flr}]) {
      if(d[(PII){i[0], i[1]}] > d[(PII){build, flr}] + i[2]) {
        d[(PII){i[0], i[1]}] = d[(PII){build, flr}] + i[2];
        que.push({d[(PII){i[0], i[1]}], i[0], i[1]});
      }
    }
  }

  if(d[{n-1, t}] >= INF) cout << -1 << endl;
  else cout << d[{n-1, t}] << endl;

  return 0;
}
0