RT

WA #5，使用迪杰斯特拉+堆优化

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <bitset>
#include <queue>
#include <algorithm>
#define maxn 50004
using namespace std;
const int INF = 0x3f3f3f3f;

int n, m;
int arr[6];
int rela[7];
int x, y, t;
int ans = INF;
int dis[maxn][7];
vector<int> edge[maxn];
map<int, int> mp[maxn];
bitset<maxn> vist;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;

void better_dijkstra(int root) {
	for(int i = 1 ; i<= n ; i++) {
		dis[i][root] = INF;
	}
	dis[rela[root]][root] = 0;
	vist.reset();
	while(!q.empty()) {
		q.pop();
	}
	q.push({0, rela[root]});
	while(!q.empty()) {
		int ben = q.top().second;
		int v = q.top().first;
		q.pop();
		if(vist[ben]) {
			continue;
		} else {
			vist[ben] = true;
		}
		for(int tmp : edge[ben]) {
			if(vist[tmp]) {
				continue;
			} else {
				if(dis[tmp][root] > v+mp[ben][tmp]) {
					dis[tmp][root] = v+mp[ben][tmp];
					q.push({dis[tmp][root], tmp});
				}
			}
		}
	}
	return ;
}

void make_edge(int L1, int L2, int V) {
	edge[L1].push_back(L2);
	mp[L1].insert({L2, V});
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 2 ; i<= 6 ; i++) {
		scanf("%d", &rela[i]);
	}
	rela[1] = 1;
	for(int i = 1 ; i<= m ; i++) {
		scanf("%d%d%d", &x, &y, &t);
		make_edge(x, y, t);
		make_edge(y, x, t);
	}
	for(int i = 1 ; i<= 6 ; i++) {
		better_dijkstra(i);
	}
	for(int i = 1 ; i<= 5 ; i++) {
		arr[i] = i+1;
	}
	for(int i = 1 ; i<= 120 ; i++) {
		int r = 0;
		for(int j = 2 ; j<= 5 ; j++) {
			r += dis[rela[arr[j-1]]][arr[j]];
		}
		r += dis[1][arr[1]];
		ans = min(ans, r);
		next_permutation(arr+1, arr+6);
	}
	printf("%d\n", ans);
	return 0;
}