2018.07.18 로곡P1171 판매원의 난제(상압dp)

전송문 느낌은 고전적인 상압 dp로 카드 상수를 아무렇게나 썼고 O(2)O(2)를 열어 물을 최적화시켰다...나는 직접 dp[i][j]dp[i][j]로 현재 i번째 점에 있고 현재 점의 선택 상황은 j(이진법으로 상태를 표시한다)를 나타낸다.이렇게 하면 직접위 연산자는 앞으로 갈 수 있는 점을 들고 상태를 옮긴다.경계는 모든 점이 한 번 빼앗겼다.코드는 다음과 같습니다.

#include
using namespace std;
int dp[21][1050000],dis[25][25],n;
inline int min(int a,int b){return aint dfs(int p,int state){
    if(dp[p][state]!=0x3f3f3f3f)return dp[p][state];
    if(state==(1<1)return dp[p][state]=dis[p][1];
    for(int i=1;i<=n;++i)if(((1<1))&state)==0)dp[p][state]=min(dp[p][state],dis[p][i]+dfs(i,state|(1<1))));
    return dp[p][state];
}
int main(){
    memset(dp,0x3f,sizeof(dp));
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            scanf("%d",&dis[i][j]);
    printf("%d",dfs(1,1));
    return 0;
}