結果

問題 No.614 壊れたキャンパス
ユーザー ferinferin
提出日時 2017-12-14 21:43:08
言語 C++11
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 2,103 bytes
コンパイル時間 2,514 ms
コンパイル使用メモリ 186,936 KB
実行使用メモリ 133,504 KB
最終ジャッジ日時 2024-12-14 13:28:56
合計ジャッジ時間 19,526 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,840 KB
testcase_01 AC 4 ms
8,036 KB
testcase_02 AC 4 ms
8,092 KB
testcase_03 AC 4 ms
7,956 KB
testcase_04 AC 4 ms
7,940 KB
testcase_05 AC 4 ms
8,128 KB
testcase_06 AC 3 ms
8,100 KB
testcase_07 AC 4 ms
7,976 KB
testcase_08 AC 1,447 ms
132,312 KB
testcase_09 AC 1,716 ms
130,392 KB
testcase_10 RE -
testcase_11 AC 1,568 ms
133,112 KB
testcase_12 AC 1,645 ms
133,256 KB
testcase_13 AC 1,591 ms
133,504 KB
testcase_14 AC 1,484 ms
133,264 KB
testcase_15 RE -
testcase_16 AC 1,374 ms
130,052 KB
testcase_17 AC 1,051 ms
108,068 KB
testcase_18 AC 1,111 ms
120,956 KB
testcase_19 AC 1,210 ms
118,016 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;
    }
    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[{i[0], i[1]}] > d[{build, flr}] + i[2]) {
        d[{i[0], i[1]}] = d[{build, flr}] + i[2];
        que.push({d[{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