[상압 dp] 클래식 TSP

0 출발 각 정점은 한 번 지나 0으로 돌아가는 최소 비용입니다.
 O($n^2\times 2^n$)
기억 검색:

 1 //  s:             v:     
 2 int dfs(int s, int v)
 3 {
 4     if(dp[s][v]>=0)
 5         return dp[s][v];
 6     if(s==(1<<n)-1 && v==0)   //           0
 7         return dp[s][v]=0;
 8     int ans=INF;
 9     for(int u=0;u<n;u++)
10         if(!(s>>(u &1))) // u         u
11             ans=min(ans, dfs(s | (1<<u), u)+mp[v][u]);
12     return dp[s][v]=ans;
13 }
14 int main()
15 {
16     memset(dp, -1, sizeof(dp));
17     printf("%d
", dfs(0, 0));
18     return 0;
19 }

 
직접 dp:

1         memset(dp, 127, sizeof(dp));
2         dp[(1<<n)-1][0]=0;
3         for(int s=(1<<n)-2;s>=0;s--)
4             for(int v=0;v<n;v++)
5                 for(int u=0;u<n;u++)
6                     if(!(s>> u & 1))
7                         dp[s][v]=min(dp[s][v], dp[s | 1<<u][u]+mp[v][u]);
8         printf("%d", dp[0][0]);