《高手训练》解题报告 3.2 最短路径

最短路径的练习题。

对应 OJ 的传送门

《高手训练》解题报告集合:信息学奥赛一本通·高手训练

未完待续。

最短路径

对于边权为正的图,任意两个结点之间的最短路径,不会经过重复的结点。

对于边权为正的图,任意两个结点之间的最短路径,不会经过重复的边。

对于边权为正的图,任意两个结点之间的最短路径,任意一条的结点数不会超过 \( n \),边数不会超过 \( n – 1 \)。

公交旅行 bus

时空限制:\(1\texttt{s},1\texttt{GiB}\)。

题目描述

在这个城市中有 \(n\) 个站台和 \(m\) 条公交线路,第 \(i\) 条公交线路由 \(t_i\) 个站台组成,记为 \(s_{i,1},s_{i,2},\cdots,s_{i,t_i}\)。在 \(0\) 时刻,第 \(i\) 辆公交车会处在 \(s_{i,1}\) 站台,之后每个时刻公交都会到达路线中的下一个站台。当公交车到达终点站后,它下一个时刻将会回到出发的站台,注意一个站台可能在一条线路中出现多次,但不会相邻。

在 \(0\) 时刻,蒜头处在站台 \(1\)。如果在某一时刻蒜头和公交在同一个站台,那么蒜头就可以上这辆公交车,并在任意时刻下车,上下车的过程并不会花费时间。现在蒜头想要知道,如果他只乘坐公交车出行,他分别能最早在何时到达每个站台,或是告诉他这是不可能的。

注意,蒜头一次只能乘坐一辆车,但在通往某个站台的过程中,蒜头可以乘坐许多辆不同的公交车。

数据范围

对于 \(100\%\) 的数据,\(n\leq 10^5\),\(m\leq 10^5\),\(t_i\geq 2\),\(\sum t_i\leq 2\times 10^5\)。

题解

考虑不建图,每次直接枚举节点转移求最短路径即可。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=1e5+5;
const int MAXM=1e5+5;
const int inf=0x3f3f3f3f;

struct Node{
	int id,val;
	inline Node(reg int id=0,reg int val=0):id(id),val(val){
		return;
	}
	inline bool operator<(const Node& a)const{
		return val<a.val;
	}
	inline bool operator>(const Node& a)const{
		return val>a.val;
	}
};

int n,m;
vector<int> bus[MAXM];
vector<int> tim[MAXN],id[MAXN];
bool vis[MAXN+MAXM];
int dis[MAXN+MAXM];
priority_queue<Node,vector<Node>,greater<Node>/**/> Q;

int main(void){
	n=read(),m=read();
	for(int i=1;i<=m;++i){
		static int x;
		x=read();
		bus[i].resize(x);
		for(int j=0;j<x;++j){
			static int s;
			s=read();
			bus[i][j]=s;
			tim[s].push_back(j);
			id[s].push_back(i);
		}
	}
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0,Q.push(Node(1,0));
	while(!Q.empty()){
		static Node s;
		s=Q.top();
		Q.pop();
		reg int u=s.id;
		if(vis[u])
			continue;
		vis[u]=true;
		if(u<=n)
			for(reg int i=0,siz=tim[u].size();i<siz;++i){
				reg int v=id[u][i]+n,d,l=bus[v-n].size();
				reg int now=dis[u]%l;
				if(tim[u][i]>=now)
					d=tim[u][i]-now+dis[u];
				else
					d=tim[u][i]-now+dis[u]+l;
				if(dis[v]>d){
					dis[v]=d;
					Q.push(Node(v,dis[v]));
				}
			}
		else
			for(reg int i=0,siz=bus[u-n].size(),t=dis[u]%siz;i<siz;++i,t=(t+1)%siz){
				reg int v=bus[u-n][t],d=dis[u]+i;
				if(dis[v]>d){
					dis[v]=d;
					Q.push(Node(v,dis[v]));
				}
			}
	}
	for(reg int i=2;i<=n;++i)
		printf("%d%c",dis[i]==inf?-1:dis[i],i==n?'\n':' ');
	return 0;
}

次短路计数 POJ3463

时空限制:\(2\texttt{s},64\texttt{MiB}\)。

题目描述

给定一张包含 \(n\) 个点、\(m\) 条边的有向图,并且给定起始点 \(s\) 和终点 \(t\),求从 \(s\) 到 \(t\) 的最短路线和比最短路线多一个单位距离的路线的总方案数。(两条路线 \(A\)、\(B\) 不同当且仅当存在一条边 \(\in A\) 且 \(\not\in B\))。

数据范围

对于 \(100\%\) 的数据,满足 \(2\leq n\leq 10^3\),\(1\leq m\leq 10^4\),\(1\leq x,y,s,t\leq n\),\(1\leq c\leq 10^3\)。

题解

最短路板子题,直接用 \(\texttt{Dijkstra}\) 算法求解最短路径即可,时间复杂度为 \(\Theta(n\log_2m)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg bool f=false;
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return f?-res:res;
}

const int MAXN=1e3+5;
const int MAXM=1e4+5;

int n,m;
int cnt,head[MAXN],to[MAXM],w[MAXM],Next[MAXM];

inline void Add_Edge(reg int u,reg int v,reg int len){
	Next[++cnt]=head[u];
	to[cnt]=v;
	w[cnt]=len;
	head[u]=cnt;
	return;
}

struct Node{
	int id,val;
	inline Node(reg int id=0,reg int val=0):id(id),val(val){
		return;
	}
	inline bool operator<(const Node& a)const{
		return val<a.val;
	}
	inline bool operator>(const Node& a)const{
		return val>a.val;
	}
};

bool vis[MAXN];
int dis[MAXN][2];
int sum[MAXN][2];
priority_queue<Node,vector<Node>,greater<Node>/**/> Q;

inline void Dijkstra(reg int s){
	memset(dis,0x3f,sizeof(dis));
	memset(sum,0x00,sizeof(sum));
	dis[s][0]=0,sum[s][0]=1,Q.push(Node(s,0));
	while(!Q.empty()){
		static Node s;
		s=Q.top();
		Q.pop();
		reg int u=s.id,k=-1;
		if(dis[u][0]==s.val)
			k=0;
		if(dis[u][1]==s.val)
			k=1;
		if(k==-1)
			continue;
		for(reg int i=head[u];i;i=Next[i]){
			reg int v=to[i];
			reg int val=s.val+w[i];
			if(dis[v][0]>val){
				dis[v][1]=dis[v][0],sum[v][1]=sum[v][0];
				dis[v][0]=val,sum[v][0]=sum[u][k];
				Q.push(Node(v,val));
			}
			else if(dis[v][0]==val)
				sum[v][0]+=sum[u][k];
			else if(dis[v][1]>val){
				dis[v][1]=val;
				sum[v][1]=sum[u][k];
				Q.push(Node(v,val));
			}
			else if(dis[v][1]==val)
				sum[v][1]+=sum[u][k];
		}
	}
	return;
}

int main(void){
	reg int T=read();
	while(T--){
		cnt=0,memset(head,0,sizeof(head));
		n=read(),m=read();
		for(reg int i=1;i<=m;++i){
			static int a,b,c;
			a=read(),b=read(),c=read();
			Add_Edge(a,b,c);
		}
		int S,T;
		S=read(),T=read();
		Dijkstra(S);
		if(dis[T][0]==dis[T][1]-1)
			printf("%d\n",sum[T][0]+sum[T][1]);
		else
			printf("%d\n",sum[T][0]);
	}
	return 0;
}

负环 cycle

时空限制:\(2\texttt{s},256\texttt{MiB}\)。

题目描述

给定一张边带权的无向图 \(G\),请你找出一个点数最少的环,使得环上的边权和为负数。保证图中不存在重边和自环。

数据范围

对于 \(100\%\) 的数据:\(2\leq n\leq 300\),\(0\leq m\leq n\times (n−1)\),\(|w_i|\leq 10^4\)。

题解

考虑倍增 \(\texttt{Floyd}\) 算法,具体地,我们设 \(\texttt{dis}_{r,i,j}\),表示经过至多 \(2^r\) 条路径,\(i,j\) 之间的最短路径。那么我们按位考虑答案,不难发现用倍增即可求得不产生负环,最多经过的边的数量,加上一即为答案。

时间复杂度 \(\Theta(n^3\log_2n)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg bool f=false;
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return f?-res:res;
}

const int MAXN=300+5;
const int MAXM=MAXN*(MAXN-1);
const int MAXLOG2N=9+1;

int n,m;
int dis[MAXLOG2N][MAXN][MAXN];
int f[MAXN][MAXN],g[MAXN][MAXN];

int main(void){
	memset(dis,0x3f,sizeof(dis));
	n=read(),m=read();
	for(reg int i=1;i<=m;++i){
		static int u,v,w;
		u=read(),v=read(),w=read();
		dis[0][u][v]=w;
	}
	for(reg int i=1;i<=n;++i)
		dis[0][i][i]=0;
	for(reg int r=1;r<MAXLOG2N;++r)
		for(reg int k=1;k<=n;++k)
			for(reg int i=1;i<=n;++i)
				for(reg int j=1;j<=n;++j)
					dis[r][i][j]=min(dis[r][i][j],dis[r-1][i][k]+dis[r-1][k][j]);
	memset(f,0x3f,sizeof(f));
	for(reg int i=1;i<=n;++i)
		f[i][i]=0;
	int ans=0;
	for(reg int r=MAXLOG2N-1;r>=0;--r){
		memset(g,0x3f,sizeof(g));
		for(reg int k=1;k<=n;++k)
			for(reg int i=1;i<=n;++i)
				for(reg int j=1;j<=n;++j)
					g[i][j]=min(g[i][j],min(dis[r][i][k]+f[k][j],f[i][k]+dis[r][k][j]));
		reg bool flag=false;
		for(reg int i=1;i<=n;++i)
			if(g[i][i]<0){
				flag=true;
				break;
			}
		if(!flag){
			ans|=(1<<r);
			for(reg int i=1;i<=n;++i)
				for(reg int j=1;j<=n;++j)
					f[i][j]=g[i][j];
		}
	}
	if(ans>=n)
		puts("0");
	else
		printf("%d\n",ans+1);
	return 0;
}

益智游戏 game

时空限制:\(2\texttt{s},256\texttt{MiB}\)。

题目描述

小 P 和小 R 在玩一款益智游戏。游戏在一个正权有向图上进行。

小 P 控制的角色要从 \(A\) 点走最短路到 \(B\) 点,小 R 控制的角色要从 \(C\) 点走最短路到 \(D\) 点。

一个玩家每回合可以有两种选择,移动到一个相邻节点或者休息一回合。

假如在某一时刻,小 P 和小 R 在相同的节点上,那么可以得到一次特殊奖励,但是在每个节点上最多只能得到一次。

求小 P 和小 R 最多能获得多少次特殊奖励。

数据范围

对于 \(100\%\) 的数据,满足 \(n\leq 5\times 10^4\),\(m\leq 2\times 10^5\),\(1\leq l_i\leq 5\times 10^8\)。

题解

考虑求出最短路径图后,最短路径图的交的最长链的节点个数即为答案。

时间复杂度 \(\Theta(n\log_2m)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=5e4+5;
const int MAXM=2e5+5;
const ll inf=0x3f3f3f3f3f3f3f3fll;

struct Edge{
	int x,y;
	ll l;
	inline Edge(reg int x=0,reg int y=0,reg ll l=0):x(x),y(y),l(l){
		return;
	}
};

struct Graph{
	int cnt,head[MAXN],to[MAXM],Next[MAXM];
	ll w[MAXM];
	inline void Add_Edge(reg int u,reg int v){
		Next[++cnt]=head[u];
		to[cnt]=v;
		head[u]=cnt;
		return;
	}
	inline void Add_Edge(reg int u,reg int v,reg ll len){
		Next[++cnt]=head[u];
		to[cnt]=v;
		w[cnt]=len;
		head[u]=cnt;
		return;
	}
	struct Node{
		int id;
		ll val;
		inline Node(reg int id=0,reg ll val=0):id(id),val(val){
			return;
		}
		inline bool operator<(const Node& a)const{
			return val<a.val;
		}
		inline bool operator>(const Node& a)const{
			return val>a.val;
		}
	};
	inline void dijkstra(reg int s,reg ll dis[]){
		static bool vis[MAXN];
		static priority_queue<Node,vector<Node>,greater<Node>/**/> Q;
		memset(vis,false,sizeof(vis));
		while(!Q.empty())Q.pop();
		dis[s]=0,Q.push(Node(s,0));
		while(!Q.empty()){
			reg int u=Q.top().id;
			Q.pop();
			if(vis[u])
				continue;
			vis[u]=true;
			for(reg int i=head[u];i;i=Next[i]){
				reg int v=to[i];
				if(dis[v]>dis[u]+w[i]){
					dis[v]=dis[u]+w[i];
					Q.push(Node(v,dis[v]));
				}
			}
		}
		return;
	}
};

int n,m;
Edge E[MAXM];
ll disa[MAXN],disb[MAXN],disc[MAXN],disd[MAXN];
Graph G1,G2,G3;
int f[MAXN],inDeg[MAXN];

int main(void){
	n=read(),m=read();
	for(reg int i=1;i<=m;++i){
		static int x,y;
		static ll l;
		x=read(),y=read(),l=read();
		E[i]=Edge(x,y,l);
		G1.Add_Edge(x,y,l);
		G2.Add_Edge(y,x,l);
	}
	int a,b,c,d;
	a=read(),b=read(),c=read(),d=read();
	memset(disa,0x3f,sizeof(disa)),memset(disb,0x3f,sizeof(disb)),memset(disc,0x3f,sizeof(disc)),memset(disd,0x3f,sizeof(disd));
	G1.dijkstra(a,disa),G1.dijkstra(c,disc),G2.dijkstra(b,disb),G2.dijkstra(d,disd);
	if(disa[b]>=inf||disc[d]>=inf)
		puts("-1");
	else{
		int ans=0;
		for(reg int i=1;i<=n;++i)
			if(disa[i]+disb[i]==disa[b]&&disc[i]+disd[i]==disc[d])
				ans=f[i]=1;
		if(!ans)
			puts("0");
		else{
			for(reg int i=1;i<=m;++i){
				reg int u=E[i].x,v=E[i].y,w=E[i].l;
				if(disa[u]+w+disb[v]==disa[b]&&disc[u]+w+disd[v]==disc[d]){
					++inDeg[v];
					G3.Add_Edge(u,v);
				}
			}
			queue<int> Q;
			for(int i=1;i<=n;++i)
				if(!inDeg[i])
					Q.push(i);
			while(!Q.empty()){
				reg int u=Q.front();
				Q.pop();
				ans=max(ans,f[u]);
				for(reg int i=G3.head[u];i;i=G3.Next[i]){
					int v=G3.to[i];
					--inDeg[v];
					f[v]=max(f[v],f[u]+1);
					if(!inDeg[v])
						Q.push(v);
				}
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

过河 river

时空限制:\(2\texttt{s},256\texttt{MiB}\)。

题目描述

EE 想搭一座跨过河的桥。河是一条无限长的宽度为 \(W\) 的直线,所有在直角坐标系中符合 \(0\leq y\leq W\) 的点都属于这条河流。

河面上有 \(N\) 个木桩,还有 \(M\) 种可以用的木头圆盘,第 \(k\) 个木桩的坐标为 \((X_k,Y_k)\)。第 \(k\) 种圆盘半径为 \(R_k\),每一块的价格为 \(C_k\)。

EE 可以买任意多的圆盘,而且他可以把它们放到河面上。每一个圆盘的中心都必须为某一个木桩的位置。注意,某些圆盘的一部分可以在地面上 \((y<0,W<y)\)。

EE 只能在直线 \(y=0\) 或直线 \(y=W\) 或圆盘上移动(相切的两者之间可以移动)。请问从直线 \(y=0\) 到直线 \(y=W\) 修建一座可以走过去的桥最少的花费。

数据范围

对于 \(100\%\) 的数据,\(1\leq T\leq 10\),\(1\leq N,M\leq 250\),\(2\leq W\leq 10^9\),\(0\leq X_k\leq 10^9\),\(1\leq Y_k\leq W\),\(1\leq R_k\leq 10^9\),\(1\leq C_k\leq 10^6\)。

题解

我们尝试着把原问题转化为最短路径问题。

考虑把每个木桩裂成 \(m\) 个节点,分别表示上面放置的圆盘的类型。

进一步地,我们可以考虑一个小优化,如果一个圆盘比另一个圆盘小且贵,那么它一定不会被选择,所以我们可以用单调栈维护出一堆半径、代价均单调递增的圆盘。

考虑优化建图,不妨从每个圆盘向后一个圆盘加边,边权为代价之差,那么求解最短路径时经过前一个圆盘走向后一个圆盘等于直接购买后面的圆盘,但是这样可以把时间复杂度将为 \(\Theta(T(n^2m+nm\log_2E))\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg bool f=false;
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return f?-res:res;
}

inline ll sqr(reg ll x){
	return x*x;
}

const int MAXN=250+5;
const int MAXM=250+5;
const int MAXV=MAXN*MAXM;
const int inf=0x3f3f3f3f;

struct point{
	int x,y;
	inline point(reg int x=0,reg int y=0):x(x),y(y){
		return;
	}
};

struct plain{
	int r,c;
	inline plain(reg int r=0,reg int c=0):r(r),c(c){
		return;
	}
	inline bool operator<(const plain& a)const{
		return r<a.r;
	}
};

struct Edge{
	int v,w;
	inline Edge(reg int v=0,reg int w=0):v(v),w(w){
		return;
	}
};

int n,m,W;
int id[MAXN][MAXM];
point pos[MAXN];
plain pie[MAXM],S[MAXM];
vector<Edge> G[MAXV];

inline void Add_Edge(reg int u,reg int v,reg int len){
	G[u].push_back(Edge(v,len));
	return;
}

struct Node{
	int id,val;
	inline Node(reg int id=0,reg int val=0):id(id),val(val){
		return;
	}
	inline bool operator<(const Node& a)const{
		return val<a.val;
	}
	inline bool operator>(const Node& a)const{
		return val>a.val;
	}
};

bool vis[MAXV];
int dis[MAXV];
priority_queue<Node,vector<Node>,greater<Node>/**/> Q;

inline int dijkstra(reg int s,reg int t){
	memset(vis,false,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	while(!Q.empty())Q.pop();
	dis[s]=0,Q.push(Node(s,0));
	while(!Q.empty()){
		reg int u=Q.top().id;
		Q.pop();
		if(vis[u])
			continue;
		vis[u]=true;
		if(u==t)
			return dis[t];
		for(vector<Edge>::iterator it=G[u].begin();it!=G[u].end();++it){
			reg int v=it->v,w=it->w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				Q.push(Node(v,dis[v]));
			}
		}
	}
	return dis[t];
}

int main(void){
	reg int T=read();
	while(T--){
		n=read(),m=read(),W=read();
		for(reg int i=1;i<=n;++i)
			pos[i].x=read(),pos[i].y=read();
		for(reg int i=1;i<=m;++i)
			pie[i].r=read(),pie[i].c=read();
		sort(pie+1,pie+m+1);
		reg int top=0;
		for(reg int i=1;i<=m;++i){
			while(top&&S[top].c>=pie[i].c)
				--top;
			S[++top]=pie[i];
		}
		m=top;
		reg int s=0,t=n*m+1,tot=0;
		for(reg int i=s;i<=t;++i)
			G[i].clear();
		for(reg int i=1;i<=n;++i)
			for(reg int j=1;j<=m;++j){
				id[i][j]=++tot;
				if(pos[i].y<=S[j].r)
					Add_Edge(s,tot,S[j].c);
				if(pos[i].y+S[j].r>=W)
					Add_Edge(tot,t,0);
			}
		for(reg int i=1;i<=n;++i)
			for(reg int j=1;j<m;++j)
				Add_Edge(id[i][j],id[i][j+1],S[j+1].c-S[j].c);
		for(reg int i=1;i<=n;++i)
			for(reg int j=i+1;j<=n;++j){
				reg int ptr=1;
				reg ll dis=sqr(pos[i].x-pos[j].x)+sqr(pos[i].y-pos[j].y);
				for(reg int k=m;k>=1;--k){
					while(ptr<=m&&sqr(S[k].r+S[ptr].r)<dis)
						++ptr;
					if(ptr<=m){
						Add_Edge(id[i][k],id[j][ptr],S[ptr].c);
						Add_Edge(id[j][k],id[i][ptr],S[ptr].c);
					}
				}
			}
		reg int ans=dijkstra(s,t);
		if(ans==inf)
			puts("impossible");
		else
			printf("%d\n",ans);
	}
	return 0;
}