最短路/次短路/K短路

2023-11-21 23:33:58

最短路

题目：poj1511
题意：n个点m条边的有向带权图，求1到所有点的最短路+除1的所有点的最短路只和。

**一开始的思路：**没注意n,m的范围（1e5），先来一波1到n，再来一波2-n到1，愉快的t了。

正解： 需要特别处理的是2-n到1的最短路，一开始确实没想到，这里感谢涛涛的讲解！
处理的话，就是把边反向建一下，再跑一遍1到所有点的的最短路，就可以了。我是**

#include <stdio.h>
#include <string>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <math.h>
#include <map>
#include <bitset>
#include <stdlib.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int , int> p;
#define mp make_pair

int t, n, m;

const int maxn = 1e6 + 100;
ll dis[maxn], vis[maxn], w[maxn];
int u[maxn], v[maxn];

struct node{
	int x;
	int w;
};

struct Node{
	int x;
	ll w;
	friend bool operator < (Node a, Node b){
		return a.w > b.w;
	}
};

priority_queue<Node> q;
vector<node>vec[maxn];

void dij(int st){
	while(!q.empty()) q.pop();
	dis[st] = 0;
	q.push((Node){st, 0});
	while(!q.empty()){
		Node c = q.top();
		q.pop();
		if(vis[c.x]) continue;
		vis[c.x] = 1;
		int len = vec[c.x].size();
		for(int i = 0; i < len; i++){
			int xx = vec[c.x][i].x;
			if(!vis[xx] && dis[c.x] + vec[c.x][i].w < dis[xx]){
				dis[xx] = dis[c.x] + vec[c.x][i].w;
				q.push((Node){xx, dis[xx]});
			}
		}
	}
}

int main(){
	scanf("%d", &t);
	while(t--){
		scanf("%d %d", &n, &m);
		for(int i = 1; i <= n; i++){
			vec[i].clear();
			dis[i] = INF;
			vis[i] = 0;
		}
		for(int i = 1; i <= m; i++){
			scanf("%d %d %lld", &u[i], &v[i], &w[i]);
			vec[u[i]].pb((node){v[i], w[i]});
		}
		dij(1);
		ll ans = 0;
		for(int i = 1; i <= n; i++){
			ans += dis[i];
		}

		for(int i = 1; i <= n; i++) vec[i].clear();
		for(int i = 1; i <= m; i++) vec[v[i]].pb((node){u[i], w[i]});

		for(int j = 1; j <= n; j++) dis[j] = INF, vis[j] = 0;
		dij(1);
		for(int i = 2; i <= n; i++) ans += dis[i];

		printf("%lld\n", ans);
	}
		
	return 0;
}

题目：hdu2066
题意：大意是有一个无向带权图共有t条边，接着给你s个起点，d个终点，问从任意起点至任意终点的最短路。
很妙的思路：（我觉得很妙，不认同我就…_：
用的优先队列优化跑的最短路，直接把s个起点塞进队列，然后直接跑最短路，最后对d的终点取min就可以了

#include <stdio.h>
#include <string>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <math.h>
#include <map>
#include <bitset>
#include <stdlib.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int t, s, d;
const int maxn = 1e3 + 5;
ll a[maxn][maxn], dis[maxn], w;
int u, v, st[maxn], ed[maxn], vis[maxn], used[maxn][maxn];

vector<int>vec[maxn];

struct node{
	ll x;
	ll w;
	friend bool operator < (node a, node b){
		return a.w > b.w;
	}
};

priority_queue<node> q;

void dij(){
	for(int i = 1; i <= s; i++){
		dis[st[i]] = 0;
	}
	while(!q.empty()){
		node c = q.top();
		q.pop();
		if(vis[c.x]) continue;
		vis[c.x] = 1;
		int len = vec[c.x].size();
		for(int i = 0; i < len; i++){
			int xx = vec[c.x][i];
			if(!vis[xx] && dis[c.x] + a[c.x][xx] < dis[xx]){
				dis[xx] = dis[c.x] + a[c.x][xx];
				q.push((node){xx, dis[xx]});
			}
		}
	}
}

void init(){
	for(int i = 0; i <= 1000; i++){
		vec[i].clear();
		dis[i] = INF;
		for(int j = 0; j <= 1000; j++){
			if(i == j)
				a[i][j] = 0;
			else
				a[i][j] = INF;
			used[i][j] = 0;
		}
		vis[i] = 0;
	}
}

int main(){
	while(~scanf("%d %d %d", &t, &s, &d)){
		init();
		for(int i = 1; i <= t; i++){
			scanf("%d %d %lld", &u, &v, &w);
			if(!used[u][v]){
				vec[u].pb(v);
				vec[v].pb(u);
			}
			used[u][v] = used[v][u] = 1;
			a[u][v] = min(a[u][v], w);
			a[v][u] = min(a[v][u], w);
		}

		for(int i = 1; i <= s; i++){
			scanf("%d", &st[i]);
			q.push((node){st[i], 0});
		}
		dij();
		for(int i = 1; i <= d; i++)	scanf("%d", &ed[i]);
		ll ans = INF;
		for(int i = 1; i <= d; i++){
			ans = min(ans, dis[ed[i]]);
		}
		cout << ans << endl;	
	}
	return 0;
}

次短路&K短路

一篇非常非常棒的博客！！！

次短路题目链接
求次短路
方法一：

#include <stdio.h>
#include <string>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <math.h>
#include <map>
#include <bitset>
#include <stdlib.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m, u, v, t;
ll w, dis1[maxn], dis2[maxn];

struct edge{
	int x;
	ll w;
};

struct node{
	int x;
	ll w;
	friend bool operator < (node a, node b){
		return a.w > b.w;
	}
};

vector <edge> vec[maxn*2];

void dij(){
	priority_queue <node> q;
	dis1[1] = 0;
	q.push((node){1, 0});
	while(!q.empty()){
		node c = q.top();
		q.pop();
		if(dis2[c.x] < c.w) continue;
		int len = vec[c.x].size();
		for(int i = 0; i < len; i++){
			int xx = vec[c.x][i].x;
			ll ww = c.w + vec[c.x][i].w;
			if(dis1[xx] > ww){
				q.push((node){xx, ww});
				swap(dis1[xx], ww);
			}
			if(dis2[xx] > ww && ww > dis1[xx]){
				dis2[xx] = ww;
				q.push((node){xx, dis2[xx]});
			}
		}
	}
}


void init(){
	for(int i = 0; i <= n; i++){
		dis1[i] = dis2[i] = INF;
		vec[i].clear();
	}
}

int main(){
	scanf("%d", &t);
	while(t--){
		scanf("%d %d", &n, &m);
		init();
		for(int i = 1; i <= m; i++){
			scanf("%d %d %lld", &u, &v, &w);
			vec[u].pb((edge){v, w});
			vec[v].pb((edge){u, w});
		}
		dij();
		printf("%lld\n", dis2[n]);
	}
	return 0;
}

方法二：
注意： 这个方法要特判一下只有一条边的情况，它会来回跑一遍，然后再跑一遍，故答案乘三

#include <stdio.h>
#include <string>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <math.h>
#include <map>
#include <bitset>
#include <stdlib.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 1e5 + 5;
int n, m, u[maxn], v[maxn], t;
ll w[maxn], dis1[maxn], dis2[maxn];
int vis[maxn];

struct edge{
	int x;
	ll w;
};

struct node{
	int x;
	ll w;
	friend bool operator < (node a, node b){
		return a.w > b.w;
	}
};

vector <edge> vec[maxn*2];

void dij(){
	priority_queue <node> q;
	priority_queue <node> q1;
	dis1[1] = dis2[n] = 0;
	q.push((node){1, 0});
	q1.push((node){n, 0});

	while(!q.empty()){
		node c = q.top();
		q.pop();
		if(vis[c.x]) continue;
		vis[c.x] = 1;
		int len = vec[c.x].size();
		for(int i = 0; i < len; i++){
			int xx = vec[c.x][i].x;
			ll ww = vec[c.x][i].w;
			if(!vis[xx] && dis1[xx] > dis1[c.x] + ww){
				dis1[xx] = dis1[c.x] + ww;
				q.push((node){xx, dis1[xx]});
			}
		}
	}
	for(int i = 1; i <= n; i++) vis[i] = 0;
	while(!q1.empty()){
		node c = q1.top();
		q1.pop();
		if(vis[c.x]) continue;
		vis[c.x] = 1;
		int len = vec[c.x].size();
		for(int i = 0; i < len; i++){
			int xx = vec[c.x][i].x;
			ll ww = vec[c.x][i].w;
			if(!vis[xx] && dis2[xx] > dis2[c.x] + ww){
				dis2[xx] = dis2[c.x] + ww;
				q1.push((node){xx, dis2[xx]});
			}
		}
	}
}

void getAns(){
	if(m == 1){
		printf("%lld\n", w[1] * 3);
		return ;
	}
	ll ans = INF;
	ll op = dis1[n];
	for(int i = 1; i <= m; i++){
		int x = u[i], y = v[i]; 
		ll tmp = dis1[x] + dis2[y] + w[i];
		if(tmp == op) continue;
		ans = min(ans, tmp);
	}
	printf("%lld\n", ans);
}

void init(){
	for(int i = 0; i <= n; i++){
		dis1[i] = dis2[i] = INF;
		vec[i].clear();
		vis[i]= 0;
	}
}

int main(){
	scanf("%d", &t);
	while(t--){
		scanf("%d %d", &n, &m);
		init();
		for(int i = 1; i <= m; i++){
			scanf("%d %d %lld", &u[i], &v[i], &w[i]);
			vec[u[i]].pb((edge){v[i], w[i]});
			vec[v[i]].pb((edge){u[i], w[i]});
		}
		dij();
		getAns();
	}
	return 0;
}
上一篇：树结构练习题


下一篇：CF125E MST Company