本题的思路是状态压缩的动态规划,由此题中所给出的数据范围以及题意,经过每个点的状态恰好可以用一个二进制数表示,而且不会超范围。那么关键就在于状态表示:由题意已知起点已给定必须是0,所以起点就大概率不应作为状态中的一个维度,而应该借用状态初始化来界定起点。
代码#include#include using namespace std; const int N=25; typedef long long ll; int w[N][N]; ll f[1<<20][N]; int main(){ int n; cin>>n; memset(f,0x3f,sizeof f); for(int i=0;i for(int j=0;j cin>>w[i][j]; } } f[1][0]=0;//状态初始化极为关键,由此就可以保证起点是0,故表示状态时并不需要起点这一元 for(int i=0;i<(1< for(int j=0;j if(i>>j&1){ for(int k=0;k if((i^(1< >k&1){ f[i][j]=min(f[i][j],f[i^(1<



