| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 538460 | 2022-03-17T02:11:37 Z | blue | Journey (NOI18_journey) | C++17 | 0 ms | 0 KB |
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int main()
{
int n, m, h;
cin >> n >> m >> h;
vector<pii> edge[n];
// cerr << "done\n";
for(int i = 0; i < n-1; i++)
{
for(int e = 0; e < h; e++)
{
int j, w;
cin >> j >> w;
if(j <= i) continue;
edge[i].push_back({j, w});
}
sort(edge[i].begin(), edge[i].end(), [] (pii x, pii y)
{
return x.second < y.second;
});
}
int dp[m][n];
for(int d = 0; d < m; d++)
for(int i = 0; i < n; i++)
dp[d][i] = 0;
dp[0][0] = 1;
for(int d = 0; d < m; d++)
{
for(int i = 0; i < n; i++)
{
if(d >= 1)
{
dp[d][i] = min(5'0000'0001, dp[d-1][i] + dp[d][i]);
}
for(pii e : edge[i])
{
if(d + e.second >= m) break;
dp[d + e.second][e.first] = min(5'0000'0001, dp[d + e.second][e.first] + dp[d][i]);
}
}
}
cout << dp[0][n-1] << ' ';
// for(int d )
for(int d = 1; d < m-1; d++) cout << dp[d][n-1] - dp[d-1][n-1] << ' ';
cout << '\n';
}