codeforces721C Journey(DP)
점 1부터 n까지 총 시간이 T인 상황에서 최대 몇 개의 도시를 지나갈 수 있느냐는 그림을 제시한다.
주요 사항:
딱 보면 DAG 안에 있는 DP라는 것을 알 수 있다. 직접 전달하는 것은 쓰기 어렵고 기억화로 검색하는 것이 편리하다. 기본적인 사고방식은 dp[i][j]메모리로 i부터 j개 도시를 통과하는 데 필요한 최소한의 시간을 저장하고 마지막에 T보다 작은 j의 최대치를 찾아내면 된다.
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 5050;
int n, m, T;
typedef pair Pair;
int dp[maxn][maxn], nex[maxn][maxn];
vector g[maxn];
bool vis[maxn];
void dfs(int u)
{
vis[u] = true;
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i].first;
int t = g[u][i].second;
if (!vis[v])
dfs(v);
for (int j = 2; j <= n; j++)
if (dp[u][j] > dp[v][j - 1] + t)
{
dp[u][j] = dp[v][j - 1] + t;
nex[u][j] = v;
}
}
}
int main()
{
int i, j;
scanf("%d%d%d", &n, &m,&T);
for (i = 1; i <= m; i++)
{
int u, v,t;
scanf("%d%d%d", &u, &v, &t);
g[u].push_back(make_pair(v, t));
}
memset(dp, 0x3f3f3f3f, sizeof(dp));
dp[n][1] = 0;
memset(nex, -1, sizeof(nex));
dfs(1);
for (int i = n; i >= 1; i--)
{
if (dp[1][i] <= T)
{
printf("%d
", i);
for (int j = 1; j != -1; j = nex[j][i], i--)
printf("%d ", j);
break;
}
}
return 0;
}
전재 대상:https://www.cnblogs.com/seasonal/p/10343661.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
