AcWing 1135. 新年好

AcWing 1135. 新年好

题目链接

 

#include
using namespace std;
typedef pair PII;
const int N = 5e5 + 10, M = 2e6 + 10,INF=0x3f3f3f3f;
int n, m;
int w[M], e[M], ne[M], h[M], idx = 0;
int dist[6][N],source[6];
bool st[N];

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dij(int start, int dist[]) {
	memset(dist, 0x3f, N * 4);
	memset(st, 0, sizeof st);
	priority_queue, greater>heap;
	dist[start] = 0;
	heap.push({ 0,start });
	while (!heap.empty()) {
		auto t = heap.top();
		heap.pop();
		int tt = t.second;
		if (st[tt])continue;
		st[tt] = true;
		for (int i = h[tt]; ~i; i = ne[i]) {
			int j = e[i];
			if (dist[j] > dist[tt] + w[i]) {
				dist[j] = dist[tt] + w[i];
				heap.push({ dist[j], j });
			}
		}
	}
}

int dfs(int u, int start, int distance) {
	if (u > 5)return distance;
	int res = INF;
	for (int i = 1; i <6; i++) {
		if (!st[i]) {
			st[i] = true;
			res = min(res, dfs(u + 1, i, distance + dist[start][source[i]]));
			st[i] = false;
		}
	}
	return res;
}
int main() {
	cin >> n >> m;
	source[0] = 1;
	for (int i = 1; i < 6; i++)cin >> source[i];
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c), add(b, a, c);
	}
	for (int i = 0; i < 6; i++)dij(source[i], dist[i]);
	memset(st,0,sizeof st);
	cout << dfs(1, 0, 0);
	return 0;
}