最短路 MEX 题解

__vector__ · 2025-05-06 11:14:13 · 题解

首先，可以使用 BFS 计算不瞬移的答案。

假设最后一次瞬移到达了 x 点，当然 x \neq s。

这意味着编号 \in [0,x-1] 的所有点都必须经过一遍。此时到达 x 点的总代价将至少是 x+1-[s \lt x]。

而如果从 s 出发就一直瞬移，直到到达 x，那么就能达到这个最小的代价。

令 dis(x,y) 代表不瞬移，仅从给定边走，从 x 到 y 的最短路径长度，令 f(x) 代表最后一次瞬移到达 x 的情况下，从 s 到 x 的最小代价。

枚举 x \in [0,n-1]，答案就是 f(x)+dis(x,t) 的最小值。

快速计算 dis，则只需要一次 bfs 预处理。

时间复杂度 O(n)。

std

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
#define gc getchar()
#define pc putchar
#define pln pc(10);
#define eb emplace_back
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
} 
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    } 
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
template<class T>
void wrint(T x){
    if(x>=10)wrint(x/10);
    pc(x%10^48);
}
const int maxn=2e5+5;
int n,m,s,t;
vi g[maxn];
int dis[maxn];
void solve(int id_of_testcase){
    read(n);
    read(m);
    read(s);
    read(t);
    FOR(i,1,m){
        int u,v;
        read(u);
        read(v);
        g[u].eb(v);
        g[v].eb(u);
    }
    FOR(i,0,n-1)dis[i]=1e9;
    queue<int> q;
    dis[t]=0;
    q.push(t);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int& v:g[u]){
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q.push(v); 
            }
        }
    }
    int ans=dis[s];
    FOR(i,0,n-1){
        int ds=dis[i]+i+1;
        if(i>=s)ds--;
        ckmn(ans,ds);
    }
    wrint(ans);
    pln
    FOR(i,0,n-1){
        g[i].clear(); 
    }
}
int main(){
    int T;
    read(T);
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}

验题人 @Tiffake 的代码：

#include<bits/stdc++.h>
#define int long long
#define pair pair<int,int>
#define fst first
#define snd second
using namespace std;
const int N=3e5+1;
int T,n,m,s,t,x,y,ans,d[N];
priority_queue<pair,vector<pair>,greater<pair>>q;
vector<int>v[N];
bitset<N>vis;
inline void dijkstra(){
    for(int i=0;i<n;i++)d[i]=INT_MAX>>2;
    d[t]=0,q.push({0,t});
    while(!q.empty()){
        int u=q.top().snd;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i:v[u]){
            if(d[i]>d[u]+1){
                d[i]=d[u]+1;
                q.push({d[i],i});
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m>>s>>t,ans=INT_MAX,vis.reset();
        for(int i=0;i<n;i++)v[i].clear();
        while(m--)cin>>x>>y,v[x].push_back(y),v[y].push_back(x);
        dijkstra();
        for(int i=0;i<s;i++)ans=min(ans,d[i]+i+1);
        for(int i=s+1;i<n;i++)ans=min(ans,d[i]+i);
        cout<<min(ans,d[s])<<'\n';
    }
    return 0;
}

验题人 @Lastkismet 的代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template<typename T> using vec=vector<T>;
template<typename T> using grheap=priority_queue<T>;
template<typename T> using lrheap=priority_queue<T,vector<T>,greater<T>>;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define per(i,x,y) for(int i=(x);i>=(y);i--)
#define repl(i,x,y) for(int i=(x);i<(y);i++)
#define file(f) freopen(#f".in","r",stdin);freopen(#f".out","w",stdout);

struct mint {
    int x,mod;
    inline mint(int o=0,int p=998244353) {x=o;mod=p;}
    inline mint & operator=(ll o){return x=o%mod,(x+=mod)>=mod&&(x-=mod),*this;}
    inline mint & operator+=(mint o){return (x+=o.x)>=mod&&(x-=mod),*this;}
    inline mint & operator-=(mint o){return (x-=o.x)<0&&(x+=mod),*this;}
    inline mint & operator*=(mint o){return x=(ll)x*o.x%mod,*this;}
    inline mint & operator^=(ll b){mint res(1);for(;b;b>>=1,*this*=*this)if(b&1)res*=*this;return x=res.x,*this;}
    inline mint & operator^=(mint o){return *this^=o.x;}
    inline mint & operator/=(mint o){return *this*=(o^=(mod-2));}
    inline mint & operator++(){return *this+=1;}
    inline mint & operator--(){return *this-=1;}
    inline mint operator++(int o){mint res=*this;return *this+=1,res;}
    inline mint operator--(int o){mint res=*this;return *this-=1,res;}
    friend inline mint operator+(mint a,mint b){return a+=b;}
    friend inline mint operator-(mint a,mint b){return a-=b;}
    friend inline mint operator*(mint a,mint b){return a*=b;}
    friend inline mint operator/(mint a,mint b){return a/=b;}
    friend inline mint operator^(mint a,ll b){return a^=b;}
    friend inline mint operator^(mint a,mint b){return a^=b;}
    friend inline bool operator<(mint a,mint b){return a.x<b.x;}
    friend inline bool operator>(mint a,mint b){return a.x>b.x;}
    friend inline bool operator<=(mint a,mint b){return a.x<=b.x;}
    friend inline bool operator>=(mint a,mint b){return a.x>=b.x;}
    friend inline bool operator==(mint a,mint b){return a.x==b.x;}
    friend inline istream & operator>>(istream &in,mint &o){ll x;return in>>x,o=x,in;}
    friend inline ostream & operator<<(ostream &ot,mint o){return ot<<o.x,ot;}
};

const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=2e5+5;

int n,m,s,t;
int dis[2][N];
vec<int> g[N];

void bfs(int be,int kd){
    queue<int> q;
    q.push(be);
    while(!q.empty()){
        int now=q.front();q.pop();
        for(auto nxt:g[now])if(dis[kd][nxt]>dis[kd][now]+1){
            dis[kd][nxt]=dis[kd][now]+1;
            q.push(nxt);
        }
    }
}

void solve(){
    cin>>n>>m>>s>>t;
    repl(i,0,n)g[i].clear(),dis[0][i]=dis[1][i]=inf;
    rep(i,1,m){
        int u,v;cin>>u>>v;
        g[u].pub(v);
        g[v].pub(u);
    }
    dis[0][s]=dis[1][t]=0;
    bfs(s,0);bfs(t,1);
    int ans=inf;
    repl(i,0,n)chmin(ans,dis[1][i]+min(dis[0][i],i+(i<=s)));
    if(ans==inf)ans=-1;
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve();
    return 0;
}