DragonBallI

The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 200 000), the number of cities andpossible teleport trips. Then follow m lines containing three space-separated integers $a_i$ , $b_i$ , and $t_i$ each (1 ≤ $a_i$ , $b_i$ ≤n, 0 ≤ $t_i$ ≤ 10 000), which, as explained above, represent the two cities connected by the teleport trip, and cost to usethe teleporter. Then follows one line of seven space-separated integers, representing the city IDs of the seven DragonBalls showing on the radar. Each ID c satisfies the bound 1 ≤ c ≤ n

C++ 解法, 执行用时: 310ms, 内存消耗: 9432K, 提交时间: 2021-08-20 10:50:19

#include<bits/stdc++.h>
using namespace std;
int getint(){ int x;scanf("%d",&x);return x; }
const int N=4e5+10;
#define ll long long
struct bian{
	int l,e,n;
};
bian b[N];
int s[N],tot=0;
void add(int x,int y,int z){
	tot++;
	b[tot].l=z;
	b[tot].e=y;
	b[tot].n=s[x];
	s[x]=tot;
}

ll dis[N];
void dij(int st){
	memset(dis,0x3f,sizeof(dis));
	dis[st]=0;
	priority_queue<pair<ll,int>>q;
	q.emplace(-dis[st],st);
	while(q.size()){
		auto [dt,t]=q.top();q.pop();
		if(dis[t]!=-dt)continue;
		for(int i=s[t];i;i=b[i].n){
			int v=b[i].e;
			if(dis[v]>dis[t]+b[i].l){
				dis[v]=dis[t]+b[i].l;
				q.emplace(-dis[v],v);
			}
		}
	}
}

int pos[10];
ll d[10][10];
int p[10];
int main(){
	int n=getint(),m=getint();
	for(int i=1;i<=m;i++){
		int x=getint(),y=getint(),z=getint();
		add(x,y,z);
		add(y,x,z);
	}
	pos[0]=1;
	for(int i=1;i<=7;i++)pos[i]=getint();
	for(int i=0;i<=7;i++){
		dij(pos[i]);
		for(int j=0;j<=7;j++)d[i][j]=dis[pos[j]];
	}
	for(int i=0;i<=7;i++)p[i]=i;
	ll ans=1e18;
	do{
		ll sum=0;
		for(int i=1;i<=7;i++)sum+=d[p[i]][p[i-1]];
		ans=min(ans,sum);
	}while(next_permutation(p+1,p+8));
	cout<<ans;
}

详情