【Acwing】最短路小trick-预处理dis数组新年好

痛定思痛。 2024-03-31 09:03 29阅读 0赞

[1135. 新年好 - AcWing题库][1135. _ - AcWing]

题意：

![3d2f50ff162342c796189075fb7ddca5.png][]

思路：

因为不知道访问的顺序，我们考虑暴力搜全排列

对于每一个全排列，我们去算一算边权和，然后维护最小值就好了

这个图是一成不变的，因此我们去预处理dis数组，维护以这5个结点为起点的dis数组，因此这是二维数组

由于编号过大，因此这里需要离散化一下

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=5e4+10,mxe=1e5+10,mnf=0x3f3f3f3f,inf=0xc0c0c0c0;
    struct ty{
        int to,next,w;
    }edge[mxe<<1];
    struct ty2{
        int x,dis;
        bool operator<(const ty2 &a)const{
            return a.dis<dis;
        }
    };
    priority_queue<ty2> q2;
    unordered_map<int,int> id;
    int n,m,x,y,w,tot=0,ans=mnf;
    int a[mxn],head[mxn],dis[7][mxn],vis[mxn];
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        id.clear();
        tot=0;ans=mnf;
        memset(dis,0x3f,sizeof(dis));
        for(int i=0;i<=n;i++){
            head[i]=-1;
            vis[i]=0;
        }
        while(!q2.empty()) q2.pop();
    }
    void init2(){
        while(!q2.empty()) q2.pop();
        memset(vis,0,sizeof(vis));
    }
    void dij(int x){
        dis[id[x]][x]=0;
        ty2 tmp;
        tmp.dis=0,tmp.x=x;
        q2.push(tmp);
        while(!q2.empty()){
            ty2 u=q2.top();
            q2.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                if(vis[edge[i].to]) continue;
                if(dis[id[x]][edge[i].to]>dis[id[x]][u.x]+edge[i].w){
                    dis[id[x]][edge[i].to]=dis[id[x]][u.x]+edge[i].w;
                    ty2 tmp2;
                    tmp2.dis=dis[id[x]][edge[i].to];
                    tmp2.x=edge[i].to;
                    q2.push(tmp2);
                }
            }
        }
    }
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin>>n>>m;
        init();
        id[1]=1;
        for(int i=2;i<=6;i++) cin>>a[i],id[a[i]]=i;
        for(int i=1;i<=m;i++){
            cin>>x>>y>>w;
            add(x,y,w);
            add(y,x,w);
        }
        dij(1);
        for(int i=2;i<=6;i++) init2(),dij(a[i]);
        /*for(int i=1;i<=6;i++){
            for(int j=1;j<=n;j++) cout<<dis[i][j]<<" ";
            cout<<'\n';
        }*/
        sort(a+2,a+2+5);
        do{
            int res=0;
            res+=dis[id[1]][a[2]];
            for(int i=2;i<=5;i++) res+=dis[id[a[i]]][a[i+1]];
            ans=min(ans,res);
        }while(next_permutation(a+2,a+2+5));
        cout<<ans<<'\n';
    }

**总结：**

**当题目中的图一成不变时，可以考虑首先维护dis数组，然后再去做别的，不需要重复求最短路，很多题都是这样的，都是求出dis数组之后再去枚举或者做点别的事，两场小白赛都有相似的应用：（虽然只是BFS求最短路，但是道理显然是一样的）**

[D-游戏购买！\_牛客小白月赛60 (nowcoder.com)][D-_60 _nowcoder.com]

这个就是先去求dis数组，然后去枚举符合条件的格点

[C-小喵觅食\_牛客小白月赛61 (nowcoder.com)][C-_61 _nowcoder.com]

这个也是先求dis数组，然后去枚举格点，维护贡献最小值

[1135. _ - AcWing]: https://www.acwing.com/problem/content/1137/
[3d2f50ff162342c796189075fb7ddca5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/8dc5f6fc1f1c45c2b8fbaa53de870f52.png
[D-_60 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/45670/D
[C-_61 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/46597/C