首页 > 其他分享 >【图论】3.26学习记录 最短路/最长路 次短路

【图论】3.26学习记录 最短路/最长路 次短路

时间：2024-03-27 18:33:05浏览次数：24  
标签：图论 dist int 短路 vis MAXN 3.26 const

最短路：

SPFA：

特点：

代码短好写，负权边必备，可以判环，容易被卡成O(nm)；

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5e5 + 10;
const int inf = 2147483647;
int dist[MAXN];
int vis[MAXN];
vector<pair<int, int> >e[MAXN];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, st;
	cin >> n >> m >> st;
	for (int i = 1; i <= n; i++) {
		dist[i] = inf;
	}
	dist[st] = 0;
	int u, v, w;
	for (int i = 1; i <= m; i++) {
		cin >> u >> v >> w;
		e[u].push_back({v, w});
		// cout<<i<<endl;
	}
	// for(int i=1;i<=n;i++){
	// 	cout<<i<<':'<<endl;
	// 	for(auto j:e[i]){
	// 		cout<<j.first<<' '<<j.second<<endl;
	// 	}
	// }
	queue<int> q;
	q.push(st);
	vis[st] = 1;
	while (!q.empty()) {
		st = q.front();
		vis[st]=0;
		q.pop();
		for (auto i : e[st]) {
			v = i.first;
			w = i.second;
			if (dist[st] + w < dist[v]) {
				dist[v] = dist[st] + w;
				if (!vis[v]) {
					q.push(v);
					vis[v] = 1;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << dist[i] << " \n"[i==n];
	}
	return 0;
}

差分约束

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int vis[MAXN];
int dist[MAXN];
int cnt[MAXN];
vector<pair<int, int> >e[MAXN];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		dist[i] = inf;
	}
	int u, v, w;
	for (int i = 1; i <= m; i++) {
		cin >> v >> u >> w;
		e[u].push_back({v, w});
	}
	for (int i = 1; i <= n; i++) {
		e[0].push_back({i, 0});
	}
	queue<int>q;
	q.push(0);
	vis[0] = 1;
	while (!q.empty()) {
		u = q.front();
		q.pop();
		vis[u] = 0;
		for (auto i : e[u]) {
			v = i.first;
			w = i.second;
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				if (!vis[v]) {
					if (++cnt[v] > n) {
						cout << "NO" << endl;
						return 0;
					}
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << dist[i] << " \n"[i == n];
	}
	return 0;
}

负环判断

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e3 + 10;
const int inf = 2147483647;
int dist[MAXN];
int vis[MAXN];
int cnt[MAXN];
vector<pair<int, int> >e[MAXN];
void sol() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		dist[i] = inf;
		vis[i] = 0;
		cnt[i] = 0;
		e[i].clear();
	}
	int u, v, w;
	for (int i = 1; i <= m; i++) {
		cin >> u >> v >> w;
		if (w >= 0) {
			e[u].push_back({v, w});
			e[v].push_back({u, w});
		}
		else {
			e[u].push_back({v, w});
		}
	}
	dist[1] = 0;
	vis[1] = 1;
	queue<int>q;
	q.push(1);
	int st;
	int f = 0;
	while (!q.empty()) {
		st = q.front();
		vis[st] = 0;
		q.pop();
		for (auto i : e[st]) {
			v = i.first;
			w = i.second;
			if (dist[st] + w < dist[v]) {
				dist[v] = dist[st] + w;
				cnt[v] = cnt[st] + 1;
				if(cnt[v] >= n){
					f=1;
					break;
				}
				if (!vis[v]) {
					q.push(v);
					vis[v] = 1;
				}
			}
		}
		if (f == 1)break;
	}
	if (f == 1)cout << "YES" << endl;
	else cout << "NO" << endl;
}
signed main() {
	int t;
	cin >> t;
	while (t--) {
		sol();
	}
}

dij

特点：

原本O(n^2)，堆优化后O(n+m log)，不能判负边

code:

堆优化版：

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

const int MAXN=2e5+10;
const int inf=2147483647;

int dist[MAXN],vis[MAXN];

struct edge{
	int dis,v;
	bool operator < (const edge &x)const{
		return x.dis<dis;
	}
};//友元函数

priority_queue<edge>pq;
vector<pair<int,int> >e[MAXN];

#define f first
#define s second

signed main(){
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		dist[i]=inf;
	}
	int u,v,w;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		e[u].push_back({v,w});
	}
	dist[s]=0;
	pq.push({0,s});
	while(!pq.empty()){
		auto j=pq.top();
		pq.pop();
		int u=j.v;
		if(vis[u])continue;
		vis[u]=1;
		for(auto i:e[u]){
			v=i.f,w=i.s;
			if(dist[u]+w<dist[v]){
				dist[v]=dist[u]+w;
				if(!vis[v]){
					pq.push({dist[v],v});
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dist[i]<<" \n"[i==n];
	}
}

最长路

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

const int MAXN=2e5+10;
const int inf=2147483647;
typedef long long ll;

ll dist[MAXN];
int vis[MAXN];

struct edge{
	int v,w;
};

vector<edge>e[MAXN];


signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,m,s;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		dist[i]=-1;
	}
	edge nd;
	int u,v,w;
	for(int i=1;i<=m;i++){
		cin>>u>>nd.v>>nd.w;
		e[u].push_back(nd);
	}
	dist[1]=0;
	int cur=1;
	while(!vis[cur]){
		vis[cur]=1;
		for(auto i:e[cur]){
			v=i.v,w=i.w;
			if(!vis[v] && (dist[cur]+w>dist[v] || dist[v]==-1)){
				dist[v]=dist[cur]+w;
			}
		}
		ll res=-1;
		for(int i=1;i<=n;i++){
			if(!vis[i] && dist[i]!=-1){
				res=dist[i];
				cur=i;
				break;
			}
		}
	}
	cout<<dist[n]<<endl;
}

次短路

顾名思义，次短路就是第二短的路，但是也有许多不同之分。

  1. 严格/不严格：长度必须小于最短路/长度可以与最短路相同
  2. 能否走重复的路：（这个重复是与自身而言，也就是可不可以来回走同一条路）

根据以上两点，可以分成四类，不过就判断好条件跑堆优化的dij就行

非严格的，不可以走重复路的次短路

例题：集合位置

思路：

1.次短路和最短路一定不是同一条，所以先跑出来最短路，记录途中到达点
2.对于最短路上每一段路进行切割，跑不含这段路的最短路，取min

code:

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

const int MAXN=205;
const int inf=1e18;
#define f first
#define s second

struct edge{
	int v;
	double dis;
	bool operator < (const edge &x)const{
		return x.dis<dis;
	}
};

priority_queue<edge>pq;
pair<double,double>P[MAXN];//存点的坐标
vector<pair<int,double> >e[MAXN];
double dist[MAXN];
int pre[MAXN],vis[MAXN];
int n,m;
int str[MAXN],cnt=0;

double len(int x,int y){
	return sqrt((P[x].s-P[y].s)*(P[x].s-P[y].s)+(P[x].f-P[y].f)*(P[x].f-P[y].f));
}

void dij(int k1,int k2){
	if(k1==-1 && k2==-1){
		int cur=1;
		for(int i=1;i<=n;i++){
			dist[i]=DBL_MAX;
		}
		dist[1]=0;
		pq.push({1,0});
		while(!pq.empty()){
			auto i=pq.top();
			pq.pop();
			int u=i.v;
			if(vis[u])continue;
			vis[u]=1;
			for(auto j:e[u]){
				int v=j.f;
				double w=j.s;
				if(dist[u]+w<dist[v]){
					pre[v]=u;
					dist[v]=dist[u]+w;
					if(!vis[v])pq.push({v,dist[v]});
				}
			}
		}
		cur=n;
		while(cur!=0){
			str[++cnt]=cur;
			cur=pre[cur];
		}
	}
	else{
		for(int i=1;i<=n;i++){
			vis[i]=0;
			dist[i]=DBL_MAX;
		}
		dist[1]=0;
		pq.push({1,0});
		while(!pq.empty()){
			auto i=pq.top();
			pq.pop();
			int u=i.v;
			if(vis[u])continue;
			vis[u]=1;
			for(auto j:e[u]){
				int v=j.f;
				double w=j.s;
				if(u==k1 && v==k2 || u==k2 && v==k1)continue;
				if(dist[u]+w<dist[v]){
					dist[v]=dist[u]+w;
					if(!vis[v])pq.push({v,dist[v]});
				}
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>P[i].f>>P[i].s;
	}
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		double w=len(u,v);
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	dij(-1,-1);
	// for(int i=1;i<=cnt;i++){
	// 	cerr<<str[i]<<" \n"[i==cnt];
	// }
	double ans=DBL_MAX;
	for(int i=1;i<cnt;i++){
		// cerr<<str[i]<<' '<<str[i+1]<<endl;
		dij(str[i],str[i+1]);
		ans=min(ans,dist[n]);
	}
	if(ans==DBL_MAX)cout<<-1<<endl;
	else printf("%.2lf",ans);
	return 0;
}

严格的，可重复的次短路

例题：Roadblocks

思路：

次短路的话可能有两种：

  1. 把最短路中的最短段重复走了一个来回
  2. 走了一段非最短路中的

最一开始是正着按照这个思路来写，想参照前一类，分别切割最短路的每一段，然后跑许多遍最短路，如果和最短路相等就找到这个路线的最短边，double算贡献。但是突然发现这个最短边比较难求，所以反着想了一下。

想了一下对于这个图里的每一条边，总共有两种可能：

  1. 是最短路的一部分
  2. 非最短路的一部分

对于前者，我们可以考虑对其double，对于后者我们就强行将其放到次短路的路径中。
至于如何判断这条边是否为最短路的一部分：
dist(1,a)+len(a,b)+dist(b,n)==dist(1,n)就是最短路的一部分

code:

//P2865 严格但是可重复路径的次短路
//1.最短路但是把最短路中的最短段重复走了一次
//2.把最短路中的一段切割出去，强制不走这一条路的最短路（注意判断是否严格）
//对于最短路上的边，double一下
//对于非最短路上的边，放进去更换一下

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

const int MAXN=5005;
const int inf=1e18;
#define f first
#define s second

int ans=inf,res;
int n,m;

struct edge{
	int dis,v;
	bool operator < (const edge &x)const{
		return x.dis<dis;
	}
};

priority_queue<edge>pq;

vector<pair<int,int>  >e[MAXN];
int vis[MAXN];
int dis1[MAXN],dis2[MAXN];

void dij(){
	for(int i=1;i<=n;i++){
		dis1[i]=inf;
		dis2[i]=inf;
	}
	dis1[1]=0;
	pq.push({0,1});
	while(!pq.empty()){
		auto j=pq.top();
		pq.pop();
		int u=j.v;
		if(vis[u])continue;
		vis[u]=1;
		for(auto i:e[u]){
			int v=i.f,w=i.s;
			if(dis1[u]+w<dis1[v]){
				dis1[v]=dis1[u]+w;
				if(!vis[v])pq.push({dis1[v],v});
			}
		}
	}
	for(int i=1;i<=n;i++){
		vis[i]=0;
	}
	dis2[n]=0;
	pq.push({0,n});
	while(!pq.empty()){
		auto j=pq.top();
		pq.pop();
		int u=j.v;
		if(vis[u])continue;
		vis[u]=1;
		for(auto i:e[u]){
			int v=i.f,w=i.s;
			if(dis2[u]+w<dis2[v]){
				dis2[v]=dis2[u]+w;
				if(!vis[v])pq.push({dis2[v],v});
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	int u,v,w;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	dij();
	for(int i=1;i<=n;i++){
		for(int j=0;j<e[i].size();j++){
			int v=e[i][j].f,w=e[i][j].s;
			if(dis1[i]+dis2[v]+w==dis1[n]){
				res=dis1[n]+2*w;
			}
			else{
				res=dis1[i]+dis2[v]+w;
			}
			ans=min(ans,res);
		}
	}
	cout<<ans<<endl;
}

标签：图论,dist,int,短路,vis,MAXN,3.26,const
From： https://www.cnblogs.com/muyi-meow/p/18097828

相关文章

  • 算法模板收集 (截至2024.3.26)
    准备线下比赛用的模板,会一直更新,但更新频率不高。找个代码托管平台放一下或许更合适,不过暂时没心思做这个。小提示:点击任意标题旁边的“显示目录导航”,再点击右上角的图钉可以固定目录。约定:所有区间操作都是在闭区间上进行的。编译器要支持gnu++11标准基本框......
  • 3.26
    今天老师给了我们组队，所以我需要对接下来的一周做一下规划，我帮扶的对象只连接了本地数据库，所以需要教会他连接远程数据库mysql，因为我自己学的是安卓连接后端连接mysql数据库，但是对于他来说这个似乎更麻烦，不巧的是对于安卓直接连mysql我也不太会，所以我还需要自己学，其实也就是对于为......
  • 3.26博客
    作业根据地域属性实现数据的可视化展示，可以看到省-市-区县三级数据下钻呈现的项目数量name为null的时候value显示为NAN因为地图该区域在数据库中没有匹配的name，所以这里count(*)直接为null，显示NAN； b->namec-<value 之前在select那里判空，没用，后来想起了地图部分在数据库......
  • 3.26毕设
    安装vite之后，”tsconfig.app.json“文件报错 鼠标移动到报错的红色下划线位置，出现错误提示“JSONschemafortheTypeScriptcompiler’sconfigurationfileOption‘–resolveJsonModule’cannotbespecifiedwithout‘node’moduleresolutionstrategy.ts”根据报......
  • 就业班 第二阶段 2401--3.26 day6 Shell初识 连接vscode
    远程连接vs_code可能出现的问题C:\Users\41703\.ssh验证远程主机的身份，如果连不上vscode，可以尝试删除这里面的公钥代码。重新安装那个扩展，排除扩展本身的问题谁连过我，并操作了什么curlhttps://gitea.beyourself.org.cn/newrain001/shell-project/raw/branch/master......
  • 2024.03.26
    周二之醍醐灌顶，前四周被MySQL高版本耽误时间，没能跟上进度。今天和一位王同学结对，经过他的讲解和演示，我完成了基础阶段。之前深受csdn毒害，教程新建项目都是选择EmptyActivity，但是项目目录中却和我的对不上，今天才得知要选择EmptyViewsActivity。代码时间2h，环境配置成功，数据......
  • 2024.03.26【版面编排】8种常见的排版构图样式，这不得多学几种
    在咱们设计之前，对元素的大致位置的构想构思叫做构图而画面的元素往往是由图片、文字和符号充当排版时就需要通过对这些元素的合理编排来达到最好的效果1.居中构图：顾名思义，我们需要将重要的元素以及主要传达的信息放置于此，让它站画面的C位，这样会使信息传达变得高效2.对称构......
  • 【图论 | 数据结构】用链式前向星存图（保姆级教程，详细图解+完整代码）
    一、概述链式前向星是一种用于存储图的数据结构，特别适合于存储稀疏图，它可以有效地存储图的边和节点信息，以及边的权重。它的主要思想是将每个节点的所有出边存储在一起，通过数组的方式连接（类似静态数组实现链表）。这种方法的优点是存储空间小，查询速度快，尤其适合于处理大规模......
  • 图论—欧拉回路/路径
    前置知识：欧拉图(两个要点：1.是连通图才有欧拉回路2.是否满足出度和入度的要求)模板题：P7771【模板】欧拉路径-洛谷|计算机科学教育新生态(luogu.com.cn)欧拉回路1.•对于无向图，欧拉回路就是在图的所有结点的度都是偶数，并且图是连通的情况下，从任意一个节点开始dfs都可......
  • 图论必备：前置知识大盘点，助你轻松起航！
    ​                        ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99