結果
問題 | No.614 壊れたキャンパス |
ユーザー |
![]() |
提出日時 | 2023-06-15 00:07:52 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,495 ms / 2,000 ms |
コード長 | 2,824 bytes |
コンパイル時間 | 4,605 ms |
コンパイル使用メモリ | 153,720 KB |
実行使用メモリ | 114,376 KB |
最終ジャッジ日時 | 2024-06-23 04:56:24 |
合計ジャッジ時間 | 14,596 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;struct Edge {int a;int b;int c;Edge(int a = -1, int b = -1, int c = -1) {this->a = a;this->b = b;this->c = c;}bool operator<(const Edge &e) const {return b < e.b;}};vector<Edge> G[200010];int main() {int N, M, K, S, T;cin >> N >> M >> K >> S >> T;for (int i = 0; i < M; ++i) {int a, b, c;cin >> a >> b >> c;G[a].push_back(Edge(a, b, c));}set<int> P[N + 1];map<int, map<int, ll>> min_cost;map<int, map<int, bool>> visited;for (int i = 1; i <= N - 1; ++i) {sort(G[i].begin(), G[i].end());}P[1].insert(S);min_cost[1][S] = 0;visited[1][S] = true;for (int i = 1; i < N; ++i) {if (G[i].empty()) {cout << -1 << endl;return 0;}if (i == 1) {for (Edge &e : G[i]) {min_cost[i][e.b] = abs(S - e.b);visited[i][e.b] = true;}} else {set<int> positions = P[i];for (Edge &e : G[i]) {positions.insert(e.b);}vector<int> B;for (int b : positions) {B.push_back(b);}{int cur_pos = *P[i].begin();ll cur_cost = min_cost[i][cur_pos];for (int b : B) {ll new_cost = cur_cost + abs(b - cur_pos);if (not visited[i][b] || min_cost[i][b] > new_cost) {min_cost[i][b] = new_cost;visited[i][b] = true;}cur_pos = b;cur_cost = min_cost[i][b];}}{int cur_pos = *P[i].rbegin();ll cur_cost = min_cost[i][cur_pos];reverse(G[i].begin(), G[i].end());reverse(B.begin(), B.end());for (int b : B) {ll new_cost = cur_cost + abs(b - cur_pos);if (not visited[i][b] || min_cost[i][b] > new_cost) {min_cost[i][b] = new_cost;visited[i][b] = true;}cur_pos = b;cur_cost = min_cost[i][b];}reverse(G[i].begin(), G[i].end());}}for (Edge &e : G[i]) {// fprintf(stderr, "i: %d, b: %d, cost: %lld\n", i, e.b, min_cost[i][e.b]);if (not visited[i + 1][e.c] || min_cost[i + 1][e.c] > min_cost[i][e.b]) {min_cost[i + 1][e.c] = min_cost[i][e.b];visited[i + 1][e.c] = true;}P[i + 1].insert(e.c);// fprintf(stderr, "%d: k: %d, cost: %lld\n", i + 1, e.c, min_cost[i + 1][e.c]);}}ll ans = LLONG_MAX;for (int k : P[N]) {ll cost = min_cost[N][k] + abs(k - T);ans = min(ans, cost);}cout << ans << endl;return 0;}