题目链接
题意
给定一个 \(N\) 个点的完全图 (有向图), 求从原点出发, 经过所有点再回到原点的最短路径长度 (可重复经过中途点)
思路
因为可多次经过同一个点, 所以可用 floyd 先预处理出每两个点之间的最短路径
接下来就是状压 dp 的部分
将已经经过的点的状态用 \(state\) 表示,
则 \(dp[state][k]\) 表示当前到达点 \(k\) 后状态为 \(state\) 时的最短路径长度
\[ans=min_{i=1}^{n}(dp[(1<<n)-1][i]+dis[i][0])\]
可用记忆化搜索
- Code
- #include
- #include
- #include
- #include
- #define F(i, a, b) for (int i = (a); i < (b); ++i)
- #define F2(i, a, b) for (int i = (a); i <= (b); ++i)
- #define dF(i, a, b) for (int i = (a); i > (b); --i)
- #define dF2(i, a, b) for (int i = (a); i >= (b); --i)
- #define maxn 12
- #define maxs 1100
- using namespace std;
- typedef long long LL;
- int n, a[maxn][maxn], dp[maxs][maxn];
- bool vis[maxs][maxn];
- void floyd() {
- F2(k, 0, n) {
- F2(i, 0, n) {
- F2(j, 0, n) {
- if (i==j||i==k||j==k) continue;
- a[i][j] = min(a[i][j],a[i][k]+a[k][j]);
- }
- }
- }
- }
- int dfs(int state, int p) {
- if (state==(1<<(p-1))) return dp[state][p] = a[0][p];
- if (vis[state][p]) return dp[state][p];
- vis[state][p] = true;
- int ans = INT_MAX, sta = state&~(1<<(p-1));
- F2(i, 1, n) {
- if (state&(1<<(i-1)) && i!=p) {
- ans = min(ans, dfs(sta, i)+a[i][p]);
- }
- }
- return dp[state][p] = ans;
- }
- void work() {
- memset(dp, 0, sizeof dp);
- memset(vis, 0, sizeof vis);
- F2(i, 0, n) {
- F2(j, 0, n) {
- scanf("%d", &a[i][j]);
- }
- }
- floyd();
- int ans = INT_MAX;
- F2(i, 1, n) ans = min(ans, dfs((1<<n)-1, i)+a[i][0]);
- printf("%d\n", ans);
- }
- int main() {
- while (scanf("%d", &n) != EOF && n) work();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2498735.html