로곡 1171 판매원의 난제상 압DP 문제풀이 보고서

제목 설명

어느 마을에 n개의 마을이 있다

입력 출력 형식

입력 형식:

마을 수 n과 각 마을 사이의 노정.

출력 형식:

가장 짧은 노정.

출력 샘플 가져오기

샘플 #1 입력:

3 0 2 1 1 0 2 2 1 0

샘플 내보내기 #1:

3 설명

입력 설명

3 {마을 수}
0 2 1 {마을1에서 마을까지의 노정}
1 0 2 {마을2에서 각 마을까지의 노정}
2 1 0 {마을 3에서 각 마을까지의 노정}

사고의 방향

스무 살을 보면 상압이 떠오른다.여기서 DP[i][j]는 i 상황에서 j까지 가는 것을 나타낸다.그냥 옮겨.옮길 수 있다면 옮길 수 있는 방정식은 dp[k][i|bit[k]=min(dp[k][i|bit[k]]]], dp[j][i]+map[j][k])이다.근데 왜 마지막 점 TLE가 됐는지 모르겠어요.그래도 그렇지, 520000~20은 걸리잖아...로곡이 홍콩 기자님이랑 똑같은 줄 알았어요.

코드

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=20+1;
const int inf=0x3f3f3f3f;
int bit[N],map[N][N],dp[N][1<<20],n,ans=inf,tot;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    n=read();
    bit[1]=1;
    memset(dp,inf,sizeof(dp));
    for (int i=2;i<=n;i++)
    bit[i]=bit[i-1]*2;
    tot=(1<1;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    map[i][j]=read();
    dp[1][1]=0;
    for (int i=1;i<=tot;i+=2)
    for (int j=1;j<=n;j++)
    if (dp[j][i]<=inf)
    {
        for (int k=1;k<=n;k++)
        if (!(i&bit[k])) dp[k][i|bit[k]]=min(dp[k][i|bit[k]],dp[j][i]+map[j][k]);
    }
    for (int i=1;i<=n;i++)
    ans=min(ans,dp[i][tot]+map[i][1]);
    printf("%d
",ans);
    return 0;
}
/*
3
0 2 1
1 0 2
2 1 0
*/

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

DP 시작 연습 6 (좋은 문제!)

번호는 11에서 nn, 번호는ii의 원료의 견고치는 ai{a i}ai이다.연금은 원료를 넣는 순서를 중시하기 때문에 작은 E {\mathrm {E} E는 반드시 1부터 n까지의 순서대로 이 원료를 연금 솥에 넣어야 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.