結果
問題 |
No.1995 CHIKA Road
|
ユーザー |
![]() |
提出日時 | 2024-05-29 15:15:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 1,104 bytes |
コンパイル時間 | 2,475 ms |
コンパイル使用メモリ | 208,156 KB |
最終ジャッジ日時 | 2025-02-21 17:08:23 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } int main() { fast_io(); int n, m; cin >> n >> m; vector<int> a(m), b(m), val; for (int i = 0; i < m; i++) { cin >> a[i] >> b[i]; val.push_back(a[i]); val.push_back(b[i]); } val.push_back(1); val.push_back(n); sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end()); int K = val.size(); vector<vector<pair<int, int>>> g(K); for (int i = 0; i < K - 1; i++) { g[i].push_back({i + 1, 2 * (val[i + 1] - val[i])}); } for (int i = 0; i < m; i++) { int u = lower_bound(val.begin(), val.end(), a[i]) - val.begin(); int v = lower_bound(val.begin(), val.end(), b[i]) - val.begin(); g[u].push_back({v, 2 * b[i] - 2 * a[i] - 1}); } vector<long long> dp(K, 1e18); dp[0] = 0; for (int i = 0; i < K; i++) { for (auto [j, w] : g[i]) { dp[j] = min(dp[j], dp[i] + w); } } cout << dp[K - 1] << "\n"; }