結果
問題 | No.561 東京と京都 |
ユーザー |
![]() |
提出日時 | 2017-08-26 00:10:58 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,513 bytes |
コンパイル時間 | 1,332 ms |
コンパイル使用メモリ | 160,320 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-15 16:52:10 |
合計ジャッジ時間 | 2,162 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> #define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++) #define REP(i,n) FOR(i,0,n) #define MOD 1000000007 #define int long long using namespace std; typedef long long ll; typedef vector<vector<ll>> mat; const int INF = 1e9; int N, D; int T[110], K[110]; struct edge { int from, to, cost; }; edge es[2010]; int d[1000]; int V, E; //s番目の頂点から各頂点への最短距離を求める void shortest_path(int s) { REP(i,V) d[i] = 1e14; d[s] = 0; while (true) { bool update = false; REP(i,E) { edge e = es[i]; if (d[e.from] != 1e14 && d[e.to] > d[e.from] + e.cost) { d[e.to] = d[e.from] + e.cost; update = true; } } if (!update) break; } } signed main() { cin >> N >> D; REP(i,N) cin >> T[i] >> K[i]; V = 4 * N + 2; E = 0; es[E++] = (edge){0, 1, 0}; for (int i=1; i<=2*N; i+=2) { es[E++] = (edge){i, i + 1, -T[i / 2]}; es[E++] = (edge){i + 2 * N + 1, i + 2 * N + 2, -K[i / 2]}; } for (int i=0; i<N; i++) { es[E++] = (edge){i * 2, i * 2 + 2 * N + 2, D}; es[E++] = (edge){i * 2, i * 2 + 1, 0}; es[E++] = (edge){i * 2 + 2 * N + 1, i * 2 + 1, D}; es[E++] = (edge){i * 2 + 2 * N + 1, i * 2 + 2 * N + 2, 0}; } shortest_path(0); /* REP(i,4*N+2) { cout << "i = " << i << " : d[i] = " << d[i] << endl; } */ cout << max(-d[2 * N], -d[4 * N + 1]) << endl; }