本文共 973 字，大约阅读时间需要 3 分钟。
题目连接：
题意：一个送披萨的，每次送外卖不超过10个地方，给你这些地方之间的时间，求送完外卖回到店里的总时间最小。
分析：跑一遍Floyd求出两两之间的最短距离，然后就是一个裸TSP问题了。
dp[state][i]表示在state状态下（state的二进制1表示经过的点）当前处于i点的的最少时间。
#include #include #include #include #include #include #include #include #include #include #include #include #define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int dis[20][20],n;int dp[1200][15];void floyd(){ for(int k=0;k<=n;k++) for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j];}int main(){ while(scanf("%d",&n)&&n) { for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) scanf("%d",&dis[i][j]); floyd(); for(int s=0;s<(1<
转载于:https://www.cnblogs.com/lienus/p/4270895.html
