LibreOJ10078. 「CQOI 2005」新年好【暴力+最短路】

10078. 「CQOI 2005」新年好

【题目描述】

传送门

【题解】

我们先算出访问节点的最短路,然后DFS枚举访问顺序就可以了。

代码如下

#include<queue>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=5e4+5,MAXM=1e5+5;
int n,m,Ans=1e9,que[10],dst[10][MAXN],a[10];
bool usd[10];
struct Edge{
    int tot,lnk[MAXN],son[MAXM<<1],nxt[MAXM<<1],W[MAXM<<1];
    void Add(int x,int y,int w){son[++tot]=y;nxt[tot]=lnk[x];W[tot]=w;lnk[x]=tot;}
}E;
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
struct xcw{
    int x,id;
    bool operator <(const xcw b)const{return x>b.x;}
};
priority_queue<xcw> hep;
bool vis[MAXN];
void DIJ(int x,int a){
    memset(dst[a],63,sizeof(dst[a]));dst[a][x]=0;
    memset(vis,0,sizeof(vis));
    while(!hep.empty()) hep.pop();hep.push((xcw){0,x});
    while(!hep.empty()){
        int k=hep.top().id,MIN=hep.top().x;hep.pop();
        if(vis[k]) continue;vis[k]=1;
        for(int j=E.lnk[k];j;j=E.nxt[j])
        if(dst[a][E.son[j]]>MIN+E.W[j]) dst[a][E.son[j]]=MIN+E.W[j],hep.push((xcw){dst[a][E.son[j]],E.son[j]});
    }
}
void Work(){
    que[0]=0;int Now=0;
    for(int i=0;i<5;i++) Now+=dst[que[i]][a[que[i+1]]];
    Ans=min(Ans,Now);
}
void DFS(int x){
    if(x>5){Work();return;}
    for(int i=1;i<=5;i++) if(!usd[i]) usd[i]=1,que[x]=i,DFS(x+1),usd[i]=0;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    n=read(),m=read();
    a[0]=1;for(int i=1;i<=5;i++) a[i]=read();
    for(int i=1,x,y,w;i<=m;i++) x=read(),y=read(),w=read(),E.Add(x,y,w),E.Add(y,x,w);
    for(int i=0;i<=5;i++) DIJ(a[i],i);
    DFS(1);
    printf("%d\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部