为啥样例没过就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