自动搬运

查看原文

来自洛谷，原作者为

	zhangyuhan 陌上人如玉，公子世无双

搬运于2025-08-24 22:14:10，当前版本为作者最后更新于2020-01-31 23:36:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

让我来仔细梳理一下题目大意，以便大家更好的编写代码。

简化一下题意，就是佳佳要依次拜访五个亲戚，给出一张图及所有人的位置，求最短距离。

首先看，$n\leq50000$，说明搜索在这题是行不通的。

要我们求最短距离，那就来考虑一下最短路。

由于她是依次不间断拜访，即到达一家后立即前往下一家，所以我们首先可以以这$6$个点为起点依次跑最短路，得到以这$6$个点为起点的最短路径。换句话说，我们知道了每两个地方间的最短距离。

接着需要定的，就是拜访顺序了。

由于只有六处，且出发点已经固定，我们就可以考虑枚举全排列，将所有的可能的拜访顺序求出，同时将每个顺序的时间求出，去所有中的最小值即可。

大体思路并不难想，也就是这样，下面让我来分析一下代码细节：

$1.$有五处亲戚。为了便于编写，我们可以不按题面输出，有一个一维数组来存储。同时，因为起点佳佳家在$1$号点，所以我们可以在这个数组的第$6$个位置存入佳佳家，这样有利于编写。

$2.$此题更新数据后卡SPFA，所以只能采用堆优化dijkstra。

$3.$由于需要求解六处的最短路径，所以存最短路径时用一般的一维数组是肯定不行的。所以我们考虑使用二维数组，其中第一维可以存储出发的亲戚家的编号，第二维跟平时定义一样。

$4.$由于求最小值，所以枚举全排列时可以剪枝：当前用时已经大于过去最小值时，就可以return。

总体就是这样。

最后分析一下时间复杂度：枚举全排列时间不大，主要在计算最短路上。采用堆优化dijkstra后，耗时为：$O(m\log n)$（常数忽略不计）

$AC$ $Code$

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define _for(i, a, b) for (int i=(a); i<=(b); i++)
#define _rep(i, a, b) for (int i=(a); i<(b); i++)
using namespace std;

typedef pair<int, int> P;
const int MAXN = 50010, INF = 1e9;

struct edge {
	int to, cost;
};
std::vector<edge> G[MAXN];
void addedge(int u, int v, int c) {
	G[u].push_back((edge){v, c});
	G[v].push_back((edge){u, c});
}//建无向边操作

int n, m, rel[7], d[7][MAXN], ans = INF;//记得ans要赋INF，以及d数组要开二维
bool vis[7];

void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P> > q;
	d[s][rel[s]] = 0;
	q.push(P(0, rel[s]));
	while (!q.empty()) {
		P p = q.top();
		q.pop();
		int v = p.second;
		if (p.first > d[s][v]) continue;
		_rep (i, 0, G[v].size()) {
			edge e = G[v][i];
			if (d[s][e.to] > d[s][v]+e.cost) {
				d[s][e.to] = d[s][v]+e.cost;
				q.push(P(d[s][e.to], e.to));
			}
		}
	}
}//标准堆优化dijkstra

void dfs(int cur, int cost, int pos) {
	if (cost > ans) return ;
	if (cur == 5) {
		ans = min(ans, cost);
		return ;
	}
	_for (i, 1, 5) 
		if (!vis[i]) {
			vis[i] = true;
			dfs(cur+1, cost+d[pos][rel[i]], i);
			vis[i] = false;
		}
}//标准枚举全排列

int main() {
	cin >> n >> m;
	_for (i, 1, 5) cin >> rel[i];
	_for (i, 1, m) {
		int u, v, c;
		cin >> u >> v >> c;
		addedge(u, v, c);
	}//建图
	rel[6] = 1;
	memset(d, 0x3f, sizeof(d));//记得d数组要初始化
	_for (i, 1, 6) dijkstra(i);
	dfs(0, 0, 6);
	cout << ans << endl;
	return 0;//完结撒花
}