图论的题目整合（Dijkstra）

发布于：2025-07-24 ⋅ 阅读:(31) ⋅ 点赞:(0)

前置知识：
Dijkstra

题目1

AT_abc070_d [ABC070D] Transit Tree Path
由于点 K K K 是固定的，并且是无向图（题目说是树），其实可以理解为求点 K K K 到点 x j x_j xj​ 的最短路加上点 K K K 到点 y j y_j yj​ 的最短路。

由于边权 c i c_i ci​ 的范围是 1 ≤ c i ≤ 1 0 9 1\le c_i\le10^9 1≤ci​≤109，没有负数，所以用 Dijkstra 以 K K K 为起点跑最短路。

#include<bits/stdc++.h>
#define int long long
#define endl putchar('\n')
using namespace std;
const int N=1e6+5;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return x*f;
}
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x<10){putchar(x+'0');return;}
	print(x/10);
	putchar(x%10+'0');
}
int n,m,k;
int T;
struct node{
	int to,dis;
	friend bool operator <(node a,node b){
		return a.dis>b.dis;
	}
};
priority_queue<node>q;
vector<node>a[N];
int dis[N];
int vis[N];
void dij(){
	for(int i=1;i<=n;i++)dis[i]=1e18;
	dis[k]=0;
	q.push(node{k,0});
	while(!q.empty()){
		node t=q.top();
		q.pop();
		int x=t.to;
		if(vis[x])continue;
		vis[x]=1;
		for(int i=0;i<a[x].size();i++){
			int y=a[x][i].to;
			int z=a[x][i].dis;
			dis[y]=min(dis[y],dis[x]+z);
			if(!vis[y])q.push(node{y,dis[y]});
		}
	}
}
signed main(){
	n=read();
	m=n-1;
	while(m--){
		int u=read(),v=read(),w=read();
		a[u].push_back(node{v,w});
		a[v].push_back(node{u,w});
	}
	T=read(),k=read();
	dij();
	while(T--){
		int x=read(),y=read();
		print(dis[x]+dis[y]);
		endl;
	}
}

题目2

题目描述
给出 N N N 个结点， M M M 条边的有向图，结点从 1 1 1 到 M M M 编号。
求最少将多少条边反向，才能至少有一条从 1 1 1 到 N N N 的路径？
例如，下图中把 3 ⟶ 2 , 7 ⟶ 4 3\longrightarrow2,7\longrightarrow4 3⟶2,7⟶4 这两条边反向，可以得到一条从 1 1 1 到 7 7 7 的路径。
也可以把 6 ⟶ 2 , 5 ⟶ 6 , 7 ⟶ 5 6\longrightarrow2,5\longrightarrow6,7\longrightarrow5 6⟶2,5⟶6,7⟶5 这三条边反向，得到一条从 1 1 1 到 7 7 7 的路径。
显然前者更优。
输入格式
第 1 1 1 行： N N N 和 M M M。
接下来 M M M 行，每行 2 2 2 个整数 u , v u, v u,v，表示一条有向边。
输出格式
第 1 1 1 行： 1 1 1 个整数，表示答案。
如果无法实现从 1 1 1 到 N N N，输出 − 1 -1 −1。

反转一条边需要一次，所以可以建一条翻转后的边但是边权为 1 1 1，再对图跑最短路（或者01BFS）。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return x*f;
}
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x<10){putchar(x+'0');return;}
	print(x/10);
	putchar(x%10+'0');
}
void putstr(string s){
	for(char v:s)putchar(v);
}
int n,m;
struct node{
	int to,dis;
	friend bool operator<(node a,node b){
		return a.dis>b.dis;
	}
};
vector<node>a[N];
int dis[N];
int vis[N];
priority_queue<node>q;
signed main(){
	n=read(),m=read();
	while(m--){
		int u=read(),v=read();
		a[u].push_back(node{v,0});
		a[v].push_back(node{u,1});
	}
	for(int i=1;i<=n;i++)dis[i]=1e18;
	q.push(node{1,0});
	dis[1]=0;
	while(!q.empty()){
		int x=q.top().to;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=0;i<a[x].size();i++){
			int y=a[x][i].to;
			int z=a[x][i].dis;
			if(dis[y]>dis[x]+z)dis[y]=dis[x]+z;
			if(!vis[y])q.push(node{y,dis[y]});
		}
	}
	if(dis[n]>=1e18)dis[n]=-1;
	print(dis[n]);
}

题目3

题目描述
给出一个有 n n n 个顶点 m m m 条边的无向连通图，每条边有一个长度 L i L_i Li​，结点编号从 1 ∼ n 1\sim n 1∼n。
求从起点 1 1 1 到终点 n n n 的最短路径的长度及其途经的各结点。
输入格式
第 1 1 1 行： 2 2 2 个整数 n n n 和 m ( n ≤ 200 , m ≤ 10000 ) m(n\le200,m\le10000) m(n≤200,m≤10000)。
接下来 m m m 行，每行 3 3 3 个整数 x , y , L i x, y, L_i x,y,Li​，表示结点 x x x 和 y y y 之间的长度为 L i L_i Li​。
输出格式
第 1 1 1 行： 1 1 1 个整数，表示 1 1 1 到 n n n 的最短距离。
第 2 2 2 行：若干个整数，表示 1 1 1 到 n n n 的最短路径经过的各结点。

根据单源最短路径改，每次找到更优的路径就标记一下它下一个点的上一个点，注意不能标记下一个点来记录路径，因为起点不止能到终点 n n n，但是终点 n n n 只能是起点到达。

#include<bits/stdc++.h>
#define int long long
//#define lc p<<1
//#define rc p<<1|1
//#define lowbit(x) x&-x
#define psp putchar(' ')
#define endl putchar('\n')
using namespace std;
const int N=1e6+5;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return x*f;
}
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x<10){putchar(x+'0');return;}
	print(x/10);
	putchar(x%10+'0');
}
void putstr(string s){
	for(char v:s)putchar(v);
}
int n,m,s;
int T;
struct node{
	int to,dis;
	friend bool operator <(node a,node b){
		return a.dis>b.dis;
	}
};
priority_queue<node>q;
vector<node>a[N];
int dis[N];
int vis[N];
int pre[N];
void dij(){
	for(int i=1;i<=n;i++)dis[i]=INT_MAX;
	dis[1]=0;
	q.push(node{1,0});
	while(!q.empty()){
		node t=q.top();
		q.pop();
		int x=t.to;
		if(vis[x]==1)continue;
		vis[x]=1;
		for(int i=0;i<a[x].size();i++){
			int y=a[x][i].to;
			int z=a[x][i].dis;
			if(dis[y]>dis[x]+z){
				dis[y]=dis[x]+z;
				pre[y]=x;
			}
			if(vis[y]==0)q.push(node{y,dis[y]});
		}
	}
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		a[u].push_back(node{v,w});
		a[v].push_back(node{u,w});
	}
	dij();
	print(dis[n]),endl;
	stack<int>t;
	while(n){
		t.push(n);
		n=pre[n];
	}
	while(!t.empty()){
		print(t.top()),psp;
		t.pop();
	}
}

题目4

题目描述
N ( 1 ≤ N ≤ 1000 ) N(1\le N\le1000) N(1≤N≤1000) 头牛要去参加一场在编号为 x ( ≤ x ≤ N ) x(\le x\le N) x(≤x≤N) 的牛的农场举行的派对。有 M ( 1 ≤ M ≤ 100000 ) M(1\le M\le 100000) M(1≤M≤100000) 条有向道路，每条路长 T i ( 1 ≤ T i ≤ 100 ) T_i(1\le T_i\le100) Ti​(1≤Ti​≤100)。
每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。求这 N N N 头牛的最短路径（一个来回）中最长的一条的长度。 特别提醒：可能有权值不同的重边。
输入格式
第 1 1 1 行： 3 3 3 个空格分开的整数 ；
第 2 … M + 1 2\ldots M+1 2…M+1 行： 3 3 3 个空格分开的整数 A i , B i , T i A_i,B_i,T_i Ai​,Bi​,Ti​，表示有一条从 A i A_i Ai​ 到 B i B_i Bi​ 的路，长度为 T i T_i Ti​。
输出格式
一行一个数，表示最长最短路的长度。

回家的最短路很简单，以 x x x 为起点跑 Dijkstra 就行了，但是图是有向图，去的路和回来的路不一样，难道以每个点为起点跑一遍 Dijkstra？其实可以用另一个邻接表存反向边，然后去的路就变成了回来的路，以 x x x 为起点对反图跑一遍最短路就行了。

#include<bits/stdc++.h>
#define int long long

//#define lc p<<1
//#define rc p<<1|1
//#define lowbit(x) x&-x
#define psp putchar(' ')

#define endl putchar('\n')

using namespace std;
const int N=1e6+5;
const int M=1e3+5;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return x*f;
}
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x<10){putchar(x+'0');return;}
	print(x/10);
	putchar(x%10+'0');
}
void putstr(string s){
	for(char v:s)putchar(v);
}
int n,m,k;
int T;
struct node{
	int to,dis;
	friend bool operator<(node a,node b){
		return a.dis>b.dis;
	}
};
vector<node>a[N];
vector<node>b[N];
int dis[N];
int dis2[N];
int vis[N];
priority_queue<node>q;
signed main(){
	//ios::sync_with_stdio(0);
	n=read(),m=read(),k=read();
	while(m--){
		int u=read(),v=read(),w=read();
		a[u].push_back(node{v,w});
		b[v].push_back(node{u,w});
	}
	for(int i=1;i<=n;i++)dis[i]=1e18;
	dis[k]=0;
	q.push(node{k,0});
	while(!q.empty()){
		int x=q.top().to;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=0;i<a[x].size();i++){
			int y=a[x][i].to;
			int z=a[x][i].dis;
			dis[y]=min(dis[y],dis[x]+z);
			if(!vis[y])q.push(node{y,dis[y]});
		}
	}
	for(int i=1;i<=n;i++)dis2[i]=1e18,vis[i]=0;
	dis2[k]=0;
	q.push(node{k,0});
	while(!q.empty()){
		int x=q.top().to;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=0;i<b[x].size();i++){
			int y=b[x][i].to;
			int z=b[x][i].dis;
			dis2[y]=min(dis2[y],dis2[x]+z);
			if(!vis[y])q.push(node{y,dis2[y]});
		}
	}
	int mx=0;
	for(int i=1;i<=n;i++)mx=max(mx,dis[i]+dis2[i]);
	print(mx);
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布