# | 제출 시각UTC-0 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1125140 | Rainmaker2627 | Toll (BOI17_toll) | C++20 | 128 ms | 48636 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int inf=1e18;
signed main() {
cin.tie(0)->sync_with_stdio(false);
int k, n, m, o, lg=0;
cin >> k >> n >> m >> o;
while (n>=(1<<lg)*k) lg++;
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(lg+1, vector<int>(k+1, inf)));
for (int i = 0; i < m; ++i) {
int a, b, t;
cin >> a >> b >> t;
dp[a][0][b%k]=t;
}
for (int f = (n-1)/k; f >= 0; --f) {
for (int r1 = 0; r1 < k; ++r1) {
for (int j = 1; j < lg; ++j) {
for (int r2 = 0; r2 < k; ++r2) {
for (int r3 = 0; r3 < k; ++r3) {
int t=dp[f*k+r1][j-1][r3];
if (t!=inf) dp[f*k+r1][j][r2]=min(dp[f*k+r1][j][r2], t+dp[(f+(1<<(j-1)))*k+r3][j-1][r2]);
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |