AcWing 1135. 新年好 （卡spfa 需要用mlogn 的堆优化dij 枚举 ）

先预处理 六个点最短路 然后暴力5!枚举即可~

注意此题卡spfa 我用双端队列优化都不行

代码语言：javascript复制

#include<bits/stdc  .h>
using namespace std;
const int N=50010,M=N<<2;
typedef pair<int,int> PII;
int e[M],idx,w[M],ne[M],h[N],sr[10],dist[10][N],res=0x3f3f3f3f,n,m;
bool st[N];
inline void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx  ;
}
inline void dij(int sr,int dis[]){
    memset(dis,0x3f,N*4);
    memset(st,0,sizeof st);
    priority_queue<PII,vector<PII>,greater<PII>>q;
    dis[sr]=0;
    q.push({0,sr});
    while(q.size()){
        auto x=q.top();
        q.pop();
        int ver=x.second;
        if(st[ver])continue;
        st[ver]=1;
        for(int i=h[ver];~i;i=ne[i]){
            int j=e[i];
            if(dis[j]>dis[ver] w[i]){
                dis[j]=dis[ver] w[i];
                q.push({dis[j],j});
            }
        }
    }
}
inline int dfs(int cnt,int now,int sum){
    if(cnt==6)return sum;
    for(int i=2;i<=6;i  ){
        if(!st[i]){
            st[i]=1;
            res=min(res,dfs(cnt 1,i,sum dist[now][sr[i]]));
            st[i]=0;
        }
    }
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    sr[1]=1;
    for(int i=2;i<=6;i  )scanf("%d",&sr[i]);
    int a,b,c;
    for(int i=1;i<=m;i  ){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    for(int i=1;i<=6;i  ){
        dij(sr[i],dist[i]);
    }
    memset(st,0,sizeof st);
    dfs(1,1,0);
    printf("%dn",res);
    
    
}

队列 优化

0 人点赞