专栏文章

国庆day1总结--上午

CCrash_Man_CHN
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minp8na8
此快照首次捕获于
2025/12/02 06:06
3 个月前
此快照最后确认于
2025/12/02 06:06
3 个月前
查看原文

最短路问题总结（暂无SPFA）

Floyd算法

思想：dp，通过中间顶点优化任意两点对最短路径
原理：i到j的最短路径 = min(直接路径, i→k→j路径),得出转移方程dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
步骤：
  1. 初始化距离矩阵（i,i都是0,其余无穷大） (初始化)
  2. 枚举中间点k，更新所有i,j的距离 (转移)
  3. 最终矩阵存所有点对最短路径 (答案)
时间复杂度: O(n^3)

实现代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2005;
int n,m,dis[maxn][maxn],e[maxn][maxn];
void floyd()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	memset(e,0x3f,sizeof e);
	cin>>n>>m;
	int cnt=0;
	for(int i=1;i<=n;i++)e[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[u][v]=min(e[u][v],w);
		e[v][u]=min(e[v][u],w);
	}
	floyd();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<e[i][j]<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

例题

1.B3647 【模板】Floyd
直接把模板打上去
2.P2888 [USACO07NOV] Cow Hurdles S
首先考虑重边用min(dp[s][e],h)，其次题目求得答案是计算出路径上最高的栏的高度的最小值.所以状态转移方程变为dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k][j]));
code
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
int dis[N][N],n,m,t; 
void floyd()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j]));
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>t;
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i<=n;i++)dis[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		int s,e,h;
		cin>>s>>e>>h;
		dis[s][e]=min(dis[s][e],h);
	}
	floyd();
	for(int i=1;i<=t;i++)
	{
		int a,b;
		cin>>a>>b;
		if(dis[a][b]<0x3f3f3f3f)cout<<dis[a][b]<<"\n";
		else cout<<"-1\n";
	}
	return 0;
}

Dijkstra算法

思想：贪心，求单源到所有顶点最短路径（边权非负）
原理：每次选最近未确定顶点，以此更新其他顶点距离
步骤：
  1. 初始化源点距离为0，其余为无穷大
  2. 选距离最小的未确定顶点，标记并更新邻点距离
  3. 重复n次，得源点到所有顶点最短路径
时间复杂度: O(m*log(n))

实现代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,s;
int dis[N];
bool vis[N];
struct node
{
	int id,w;
	bool operator < (const node & tmp) const
	{
		return w>tmp.w;
	}
};
vector<node> e[N];
priority_queue<node> pq;
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	pq.push({s,dis[s]});
	while(!pq.empty())
	{
		node t=pq.top();
		pq.pop();
		int x=t.id;
		if(vis[x]==1)continue;
		vis[x]=1;
		for(int i=0;i<e[x].size();i++)
		{
			int y=e[x][i].id;
			int w=e[x][i].w;
			if(dis[x]+w<dis[y])
			{
				dis[y]=dis[x]+w;
				pq.push({y,dis[y]});
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back({v,w});
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}

例题

1.P4779 【模板】单源最短路径（标准版）
模板题
2.P4568 [JLOI2011] 飞行路线
首先用优先队列，然后用重载运算符，但是这道题目有两种情况 1.没用优惠 2.用了优惠，所以我们要写两个判断，最后所有起点一律从1开始即可
code
CPP
v#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,k,s,t;
int dis[N][15];
bool vis[N][15];
struct node
{
	int id,w,cnt;
	bool operator < (const node & tmp) const
	{
		return w>tmp.w;
	}
};
vector<node> e[N];
priority_queue<node> pq;
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof(vis));
	dis[s][0]=0;
	pq.push({s,dis[s][0],0});
	while(!pq.empty())
	{
		node t=pq.top();
		pq.pop();
		int x=t.id,l=t.cnt;
		if(vis[x][l]==1)continue;
		vis[x][l]=1;
		for(int i=0;i<e[x].size();i++)
		{
			int y=e[x][i].id;
			int w=e[x][i].w;
			if(dis[x][l]+w<dis[y][l])
			{
				dis[y][l]=dis[x][l]+w;
				pq.push({y,dis[y][l],l});
			}
			if(l<k&&dis[x][l]+0<dis[y][l+1])
			{
				dis[y][l+1]=dis[x][l]+0;
				pq.push({y,dis[y][l+1],l+1});
			}
		}
	}
	return ;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k>>s>>t;
	s++,t++;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		u++,v++;
		e[u].push_back({v,w});
		e[v].push_back({u,w});		
	}
	dijkstra(s);
	int ans=1e18;
	for(int i=0;i<=k;i++)ans=min(ans,dis[t][i]);
	cout<<ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...