题解 P5764 【[CQOI2005]新年好】

Blue_wonders · 2020-01-30 12:36:31 · 个人记录

先提醒一下没做这道题的人，这道题加强数据之后朴素以及双端队列优化的 SPFA 是过不去的，朴素的 dijkstra 也过不去。

这篇题解主要是堆优化的(priority+pair)spfa

思路

• 这道题因为去的顺序不一定，所以要跑6遍单源最短路，找到每一个节点之间的最短路。
• 这是后就可以把这些最短路径缩成一个6x6的完全图。
• 最后爆搜一遍，即可得到答案。

  过程

• 道理很简单，但是我想用 SPFA ，虽然可能被卡，但是我用他的理由是他写起来简单，行数少一点。
• 所以我经过各种修改，尝试各种优化，最终发现这样一种方法可以通过这道题。(虽然已经和 dijkstra 相差不大)

  代码实现

AC详情

#include<cstdio>
#include<vector>
#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#define re register int
using namespace std;
int read(){
    int xxx=0,fu=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fu=-fu;ch=getchar();}
    while(ch>='0'&&ch<='9')xxx=xxx*10+ch-'0',ch=getchar();
    return xxx*fu;
}

int n,m,a,b,c;
int ma[6][6],cl[6],ans=0x3f3f3f3f;
int aim[6];
struct node{
    int to,val;
};
vector<node>h[50001];

int dfs(int s,int me){
    int ti=0;
    for(re i=1;i<=5;i++){
        if(i==s)continue;
        if(cl[i]==0){
            cl[i]++;
            dfs(i,me+ma[s][i]);
            cl[i]--;
        }
        else ti++;
    }
    if(ti==4)ans=min(ans,me);
    return ans;
}

int vis[50001],d[50001];
typedef pair<int,int>pa;  
priority_queue<pa,vector<pa>,greater<pa> >q;
void priority_spfa(int num,int s){
    memset(d,0x3f3f3f3f,sizeof(d));
    vis[s]=1;d[s]=0;
    q.push(make_pair(0,s));
    while(q.size()!=0){
        int u=q.top().second;
        int x=q.top().first;
        q.pop();vis[u]=0;
        if(x>d[u])continue;
        for(re i=0;i<h[u].size();i++){
            node v=h[u][i];
            if(d[u]+v.val<d[v.to]){
                d[v.to]=d[u]+v.val;
                vis[v.to]=1;
                q.push(make_pair(d[v.to],v.to));
            }
        }
    }
    ma[num][0]=d[1];
    ma[num][1]=d[aim[1]];
    ma[num][2]=d[aim[2]];
    ma[num][3]=d[aim[3]];
    ma[num][4]=d[aim[4]];
    ma[num][5]=d[aim[5]];
}
int main(){
    n=read();m=read();
    for(re i=1;i<=5;i++)aim[i]=read();
    for(re i=1;i<=m;i++){
        a=read();b=read();c=read();
        h[a].push_back((node){b,c});
        h[b].push_back((node){a,c});
    }
    priority_spfa(0,1);
    priority_spfa(1,aim[1]);
    priority_spfa(2,aim[2]);
    priority_spfa(3,aim[3]);
    priority_spfa(4,aim[4]);
    priority_spfa(5,aim[5]);
    printf("%d",dfs(0,0));
    return 0;
}