CF719-div.3 G. To Go Or Not To Go?题解

可以O(nm)的吧..三遍bfs即可。

题意：在一个矩阵迷宫中从起点跑到终点，中间有一些带权中转站，任意中转站两两可以互达，耗费两个中转站的权值和。求最小花费。

在任意中转站之间多次跳动是不优的。故只需要分为使用和未使用中转站的情况。未使用的情况就是简单的跑迷宫，bfs即可。使用的情况下，需从起点跑到花费最小的一个中转站，终点亦然。于是从起点和终点分别跑一遍bfs，更新可以中转的地方的\(???????????+a_{i,j}\)的最小值即可。两种情况的较小值就是答案。

在洛谷讨论贴上发现还有跑dij跑过去的...跑dij大概需要惊人的卡常技巧..?反正构图我就没想出怎么简化...

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl ‘\n‘
#define ll long long
#define int ll
const int maxn=2e3+10;
const ll inf=1e16;
int tu[maxn][maxn];
int n,m,w,ans=inf;
struct node{
    int x1;int y1;int co;
};
bool vis[maxn][maxn];
int mix,miy,minz=inf,weix,weiy,minw=inf,cntb;
void bfs1(int x1,int y1,int co){
    queue<node> k1;
    k1.push((node){x1,y1,0});
    while(!k1.empty()){
        node tmp=k1.front();k1.pop();
        if(tu[tmp.x1][tmp.y1]){
            if(tmp.co+tu[tmp.x1][tmp.y1]<minz){
                minz=tmp.co+tu[tmp.x1][tmp.y1];
                mix=tmp.x1,miy=tmp.y1;
            }
        }
        if(vis[tmp.x1][tmp.y1]) continue;
        vis[tmp.x1][tmp.y1]=1;
        x1=tmp.x1;y1=tmp.y1;co=tmp.co;
        if(x1-1>0&&tu[x1-1][y1]!=-1) k1.push((node){x1-1,y1,co+w});
        if(x1+1<=n&&tu[x1+1][y1]!=-1) k1.push((node){x1+1,y1,co+w});
        if(y1-1>0&&tu[x1][y1-1]!=-1) k1.push((node){x1,y1-1,co+w});
        if(y1+1<=m&&tu[x1][y1+1]!=-1) k1.push((node){x1,y1+1,co+w});
    }
}
void bfs(int x1,int y1,int co){
    queue<node> k1;
    k1.push((node){x1,y1,0});
    while(!k1.empty()){
        node tmp=k1.front();k1.pop();
        if(tu[tmp.x1][tmp.y1]==-1){
            continue;
        }
        if(tmp.x1==n&&tmp.y1==m){
            ans=min(ans,tmp.co);
            return;
        }
        if(vis[tmp.x1][tmp.y1]) continue;
        vis[tmp.x1][tmp.y1]=1;
        x1=tmp.x1;y1=tmp.y1;co=tmp.co;
        if(x1-1>0&&tu[x1-1][y1]!=-1) k1.push((node){x1-1,y1,co+w});
        if(x1+1<=n&&tu[x1+1][y1]!=-1) k1.push((node){x1+1,y1,co+w});
        if(y1-1>0&&tu[x1][y1-1]!=-1) k1.push((node){x1,y1-1,co+w});
        if(y1+1<=m&&tu[x1][y1+1]!=-1) k1.push((node){x1,y1+1,co+w});
    }
}
signed main(){
    ios;
    cin>>n>>m>>w;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>tu[i][j];
        }
    }
    bfs1(n,m,0);
    weix=mix,weiy=miy,minw=minz;minz=inf;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) vis[i][j]=0;
    }
    bfs1(1,1,0);
    ans=min(ans,minz+minw);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) vis[i][j]=0;
    }
    bfs(1,1,0);
    if(ans==inf) cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

CF719-div.3 G. To Go Or Not To Go?题解

原文：https://www.cnblogs.com/14long-Alex/p/14736017.html