UVa 116 Unidirectional TSP(일반 여행사 DP)
6226 단어 uva
대가가 가장 적은 경로를 구하다.
아이디어:
경로가 필요하고 사전의 순서가 가장 작은 서열을 출력해야 하기 때문이다.그래서 DP를 역으로 구하고 dfs를 모방하면 문제 풀이의 난이도를 낮출 수 있다.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define min(a,b) (((a) < (b)) ? (a) : (b))
int map[15][105];
int dp[15][105], path[15][105];
int n, m;
int main()
{
while (scanf("%d %d", &n, &m) != EOF)
{
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
scanf("%d", &map[i][j]);
memset(dp, 0, sizeof(dp));
memset(path, 0,sizeof(path));
for (int j = m - 1; j >= 0; --j)
{
for (int i = 0; i < n; ++i)
{
int a = dp[(i-1+n)%n][j+1];
int b = dp[i][j+1];
int c = dp[(i+1)%n][j+1];
int mm;
if (a > b)
mm = min(b, c);
else
mm = min(a, c);
dp[i][j] = map[i][j] + mm;
path[i][j] = 1e9;
if (mm == a)
path[i][j] = (i - 1 + n) % n;
if (mm == b)
path[i][j] = min(path[i][j], i);
if (mm == c)
path[i][j] = min(path[i][j], (i + 1) % n);
}
}
int ans = 1e9;
int id;
for (int i = 0; i < n; ++i)
if (ans > dp[i][0])
ans = dp[i][0], id = i;
printf("%d", id + 1);
id = path[id][0];
for (int j = 1; j < m; ++j)
{
printf(" %d", id + 1);
id = path[id][j];
}
printf("
%d
", ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA - 10986 Sending email(Dijkstra 인접 테이블 + 우선 순위 대기열 최적화)제목 대의: s점에서 t점까지의 최소 거리를 구하는 그림을 주세요. 확인: 적나라한 최단길이지만 n이 너무 크면 인접 행렬을 사용할 수 없기 때문에 Dijkstra에 대한 인접표 + 우선 대기열 최적화가 필요합니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.