結果
問題 | No.614 壊れたキャンパス |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;#define int lltypedef 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 intconst ll INF = (1LL<<60);#elseconst int INF = (1LL<<30);#endifconst 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, costg[{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;}