我有大大的疑问
查看原帖
我有大大的疑问
806928
f13825726391楼主2024/8/18 22:06

为啥样例没过就AC了?

附代码:

#include<bits/stdc++.h>
#define P pair<int,int>
using namespace std;
const int N=5000005;
int p,n,m,ans=0x3f3f3f3f;
int d[10][N],re[50],he[N],v[N];
struct U{
	int ne,to,cost;
}w[N];
priority_queue<P,vector<P>,greater<P> >q;
void add(int x,int y,int l){
	w[++p].ne=he[x];
	w[p].to=y;
	w[p].cost=l;
	he[x]=p;
}
void dijk(int s){
	for(int i=1;i<=n;i++) d[s][i]=0x3f3f3f3f;
	memset(v,0,sizeof(v));
	d[s][re[s]]=0;
	q.push(make_pair(0,re[s]));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(v[x]) continue;
		v[x]=1;
		for(int i=he[x];i;i=w[i].ne){
			if(d[s][x]+w[i].cost<d[s][w[i].to]){
				d[s][w[i].to]=d[s][x]+w[i].cost;
				q.push(make_pair(d[s][w[i].to],w[i].to));
			}
		}
	}
}
void o(int now,int times,int cost){
	if(cost>ans) return;
	if(times==5){
		ans=min(ans,cost);
		return;
	}
	for(int i=1;i<=5;i++){
		if(i!=now&&!v[i]){
			v[i]=1;
			o(i,times+1,cost+d[now][re[i]]);
			v[i]=0;
		}
	}
}
int main(){
	cin>>n>>m;
	int x,y,l;
	for(int i=1;i<=5;i++){
		cin>>re[i];
	}
	re[6]=1;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>l;
		add(x,y,l);add(y,x,l);
	}
	for(int i=1;i<=6;i++){
		dijk(i);
	}
	memset(v,0,sizeof(v));
	o(6,0,0);
	cout<<ans<<endl;
	return 0;
}

求dalao解惑QWQ

2024/8/18 22:06
加载中...