結果
問題 | No.614 壊れたキャンパス |
ユーザー |
![]() |
提出日時 | 2017-12-14 20:44:29 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,324 ms / 2,000 ms |
コード長 | 2,222 bytes |
コンパイル時間 | 2,327 ms |
コンパイル使用メモリ | 189,504 KB |
実行使用メモリ | 80,184 KB |
最終ジャッジ日時 | 2024-12-14 13:25:02 |
合計ジャッジ時間 | 16,404 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define all(v) (v).begin(), (v).end()#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)#define rep(i, n) reps(i, 0, n)template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}using Pi = pair<int, int>;using Ti = tuple<int, int, int>;using vint = vector<int>;const int inf = 1LL << 55;const int mod = 1e9 + 7;struct edge {int to, cost;edge(){}edge(int to, int cost):to(to), cost(cost){}};using Graph = vector<vector<edge>>;signed main(){cin.tie(0);ios_base::sync_with_stdio(0);cout << fixed << setprecision(12);int N, M, K, S, T;cin >> N >> M >> K >> S >> T;--S, --T;map<int, int> mp;vector<vint> buil(N);int sz = 0;mp[S] = sz++;buil[0].push_back(S);mp[(N-1)*K+T] = sz++;buil[N-1].push_back(T);vint a(M), b(M), c(M);rep(i, M) {cin >> a[i] >> b[i] >> c[i];--a[i], --b[i], --c[i];if(!mp.count(a[i]*K+b[i])) {mp[a[i]*K+b[i]] = sz++;buil[a[i]].push_back(b[i]);}if(!mp.count((a[i]+1)*K+c[i])) {mp[(a[i]+1)*K+c[i]] = sz++;buil[a[i]+1].push_back(c[i]);}}Graph graph(sz);rep(i, N) {sort(all(buil[i]));rep(j, buil[i].size()-1) {int s = mp[i*K+buil[i][j]];int t = mp[i*K+buil[i][j+1]];int cost = buil[i][j+1]-buil[i][j];graph[s].emplace_back(t, cost);graph[t].emplace_back(s, cost);}}rep(i, M) {int s = mp[a[i]*K+b[i]];int t = mp[(a[i]+1)*K+c[i]];graph[s].emplace_back(t, 0);}vint mincost(sz, inf);priority_queue<Pi, vector<Pi>, greater<Pi>> que;mincost[mp[S]] = 0;que.emplace(0, mp[S]);while(!que.empty()) {Pi p = que.top(); que.pop();int v = p.second;if(mincost[v] < p.first) continue;if(v == mp[(N-1)*K+T]) {cout << mincost[v] << endl;return 0;}for(edge& e : graph[v]) {if(mincost[e.to] > mincost[v]+e.cost) {mincost[e.to] = mincost[v]+e.cost;que.emplace(mincost[e.to], e.to);}}}cout << -1 << endl;return 0;}