結果
問題 | No.1995 CHIKA Road |
ユーザー |
![]() |
提出日時 | 2024-12-01 16:21:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 303 ms / 2,000 ms |
コード長 | 1,269 bytes |
コンパイル時間 | 2,531 ms |
コンパイル使用メモリ | 213,176 KB |
最終ジャッジ日時 | 2025-02-26 10:02:25 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> #define inf 2000000000 using namespace std; using Pair = pair<int, int>; int main(){ int n, m; cin >> n >> m; vector<pair<int, int> > edges(m); for(auto&[x, y] : edges){ cin >> x >> y; --x, --y; } vector<int> V = {0, n - 1}; for(auto&[x, y] : edges){ V.push_back(x); V.push_back(y); } sort(V.begin(), V.end()); V.erase(unique(V.begin(), V.end()), V.end()); int N = (int)V.size(); unordered_map<int, int> mp = {}; for(int i = 0; i < N; ++i){ mp[V[i]] = i; } vector<vector<Pair> > graph(N, vector<Pair>({})); for(int i = 0; i < N; ++i){ graph[i].push_back({i + 1, 2 * (V[i + 1] - V[i])}); } for(auto&[x, y] : edges){ graph[mp[x]].push_back({mp[y], 2 * y - 2 * x - 1}); } vector<int> dp(N, inf); priority_queue<Pair, vector<Pair>, greater<Pair> > pq; pq.push({0, 0}); while(!pq.empty()){ auto[c, v] = pq.top(); pq.pop(); if(dp[v] <= c){ continue; } dp[v] = c; if(v == N - 1){ break; } for(auto&[nv, nd] : graph[v]){ pq.push({c + nd, nv}); } } cout << dp[N - 1] << endl; return 0; }