2 条题解

  • 0
    @ 2025-10-5 22:08:42

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

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

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

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

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

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

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

    时间复杂度 O(n)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;
}
    • 0
      @ 2025-9-12 22:53:25

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

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

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

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

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

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

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

      时间复杂度 O(n)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;
}
      • 1

      [User Entry] 最短路

      信息

      ID
      203
      时间
      1000ms
      内存
      512MiB
      难度
      6
      标签
      递交数
      5
      已通过
      4
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      2. Source Code Modified by Sleeping Cup
      3. Worker 0, 45ms
      4. Powered by Hydro v5.0.7 Community