結果

問題 No.614 壊れたキャンパス
ユーザー ferinferin
提出日時 2017-12-14 21:46:49
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 1,742 ms / 2,000 ms
コード長 2,149 bytes
コンパイル時間 2,147 ms
コンパイル使用メモリ 187,072 KB
実行使用メモリ 133,468 KB
最終ジャッジ日時 2024-12-14 13:29:55
合計ジャッジ時間 19,811 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0