题意分析

题目描述了一个披萨店的最短路径配送问题：

1. 只有一个司机需要配送多个订单（1-10个）
2. 需要找到从披萨店（0号点）出发，经过所有配送点（1-n号点）至少一次后返回披萨店的最短路径
3. 允许重复经过任何地点
4. 路径时间矩阵可能不对称（i→j和j→i时间可能不同）

解题思路

这是一个典型的旅行商问题（TSP）变种，可以采用以下方法解决：

1. Floyd预处理：

   • 先用Floyd算法计算所有点对之间的最短路径
   • 因为题目允许重复经过点，所以实际最优路径可能包含间接路径

2. 状态压缩DP：

   • 使用二进制数表示已访问的点集合（状态压缩）
   • dp[state][u]表示在state状态下当前位于u点的最小时间
   • 状态转移：dp[state|(1<<v)][v] = min(dp[state][u] + G[u][v])

3. 初始化和终止条件：

   • 初始状态：只访问过0号点，dp[1][0] = 0
   • 终止状态：所有点都访问过并返回0号点

优化后的标程代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
int G[15][15];
int dp[1<<15][15];

int main() {
    int n;
    while(scanf("%d", &n) && n) {
        // 输入时间矩阵
        for(int i=0; i<=n; i++) 
            for(int j=0; j<=n; j++) 
                scanf("%d", &G[i][j]);
        
        // Floyd算法计算所有点对最短路径
        for(int k=0; k<=n; k++)
            for(int i=0; i<=n; i++)
                for(int j=0; j<=n; j++)
                    G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
        
        // 初始化DP数组
        memset(dp, 0x3f, sizeof(dp));
        dp[1][0] = 0;  // 初始状态：只访问过0号点
        
        // 状态压缩DP
        for(int state=1; state<(1<<(n+1)); state+=2) {  // 保证0号点始终被访问
            for(int u=0; u<=n; u++) {
                if(!(state&(1<<u))) continue;  // 当前状态未访问u点则跳过
                for(int v=0; v<=n; v++) {
                    int new_state = state|(1<<v);
                    dp[new_state][v] = min(dp[new_state][v], dp[state][u]+G[u][v]);
                }
            }
        }
        
        // 输出结果：访问所有点后返回0号点的最短时间
        printf("%d\n", dp[(1<<(n+1))-1][0]);
    }
    return 0;
}

代码说明

1. 输入处理：

   • 读取n和(n+1)×(n+1)的时间矩阵

2. Floyd预处理：

   • 三层循环计算所有点对之间的最短路径
   • 处理了间接路径可能更优的情况

3. DP初始化：

   • dp数组初始化为INF
   • 初始状态设置为只访问过0号点（二进制最低位为1）

4. 状态转移：

   • 外层循环枚举所有可能的状态
   • 内层循环进行状态转移，更新到达每个点的最短时间

5. 结果输出：

   • 最终状态是所有点都访问过（全1状态）并回到0号点

该算法的时间复杂度为O(n^3 + 2^n * n^2)，对于n≤10的数据规模完全可以在合理时间内完成。

经典的旅行商问题（TSP），使用动态规划结合状态压缩来求解最短路径。

算法原理

问题定义：
给定n个城市和城市间的距离，求从起点（0号城市）出发，访问所有城市一次后返回起点的最短路径。

核心思路：
状态压缩：用位掩码i表示已访问的城市集合（如i=0b101表示已访问第1和第3个城市）。
动态规划：定义dp[i][j]为「已访问城市集合为i，当前在城市j时的最短路径长度」。
状态转移：
初始状态：dp[1<<(j-1)][j] = dis[0][j]（仅访问城市j时，路径为起点到j的直接距离）。
转移方程：dp[i][j] = min(dp[i^(1<<(j-1))][k] + dis[k][j])，其中k是已访问的其他城市。

预处理：
使用Floyd算法计算所有城市对之间的最短路径，确保dis[i][j]存储的是i到j的最小距离。

结果计算：
遍历所有城市j，取dp[(1<<n)-1][j] + dis[j][0]的最小值（表示访问所有城市后从j返回起点的总距离）。

关键步骤

1 Floyd算法：计算任意两点间的最短路径，处理可能的间接路径更短的情况。
状态初始化：仅访问单个城市时，路径为起点到该城市的直接距离。
状态转移：枚举所有已访问城市集合和当前所在城市，更新最短路径。
结果汇总：考虑所有可能的终点，加上返回起点的距离，取最小值。

总结

该算法通过状态压缩动态规划高效解决了小规模TSP问题，将「已访问城市集合」和「当前位置」编码为状态，通过状态转移逐步构建最优解，是解决组合优化问题的经典方法。

#include<iostream>
#include<string>
#include<map>
#include<set>
//#include<unordered_map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<bitset>
#include<fstream>
#define X first
#define Y second
#define best 131 
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define lowbit(x) x & -x
#define inf 0x3f3f3f3f
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
//#define int long long
//#define double long double
//#ifndef ONLINE_JUDGE  freopen("data.in.txt","r",stdin);
//freopen("data.out.txt","w",stdout); #endif //???t?áè? 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const int Mod=998244353;
const double eps=1e-9;
const int N=26;
const int mod=1e8;
const int maxn=1e6+10;



int n,m,dis[12][12];
int dp[1<<12][12]; 

int main()																						
{	

	while(cin>>n)
	{
		if(n==0) break;
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				cin>>dis[i][j];
		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];
		for(int i=0;i<(1<<n);i++)
			for(int j=1;j<=n;j++)
					dp[i][j]=inf;
		for(int i=0;i<(1<<n);i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i&(1<<(j-1)))//如果经过这个城市
				{
					if(i==(1<<(j-1))) dp[i][j]=dis[0][j];
					else
					{
						for(int k=1;k<=n;k++)
							if(i&(1<<(k-1))&&j!=k)
								dp[i][j]=min(dp[i][j],dp[i^(1<<(j-1))][k]+dis[k][j]);
					}
				}
			}
		}
		int ans=inf;
		for(int i=1;i<=n;i++)
			ans=min(ans,dp[(1<<n)-1][i]+dis[i][0]);
		cout<<ans<<endl;
	}
	return 0;
}