Acwing 1135 新年好

重庆城里有 n 个车站，m 条 双向 公路连接其中的某些车站。

每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。

在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 1，他有五个亲戚，分别住在车站 a,b,c,d,e

过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。

怎样走，才需要最少的时间？

输入格式

第一行：包含两个整数 n,m 分别表示车站数目和公路数目。

第二行：包含五个整数 a,b,c,d,e 分别表示五个亲戚所在车站编号。

以下 m 行，每行三个整数 x,y,t 表示公路连接的两个车站编号和时间。

输出格式

输出仅一行，包含一个整数 T，表示最少的总时间。

数据范围

1 ≤ n ≤ 50000 1≤n≤50000 1≤n≤50000
1 ≤ m ≤ 1 0 5 1≤m≤10^5 1≤m≤105
1 < a , b , c , d , e ≤ n 1<a,b,c,d,e≤n 1<a,b,c,d,e≤n
1 ≤ x , y ≤ n 1 ≤ x , y ≤ n 1≤x,y≤n1≤x,y≤n 1≤x,y≤n1≤x,y≤n
1 ≤ t ≤ 100 1≤t≤100 1≤t≤100

思路

本题会卡掉spfa 所以用堆优化的Dijkstra做

先预处理 每个点到其他点的最短距离

再 d f s dfs dfs暴力枚举访问的顺序 取最小值

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
const int N = 500010, INF = 0x3f3f3f3f;
int n, m;

int dist[6][N];
int source[6];
bool st[N];
vector<pair<int, int>>vec[N];

void dijkstra(int start, int dist[]) {
	memset(dist, 0x3f, N * 4);
	dist[start] = 0;
	memset(st, false, sizeof st);

	priority_queue<PII, vector<PII>, greater<PII>>heap;
	heap.push({ 0,start });
	

	while (!heap.empty()) {
		auto t = heap.top();
		heap.pop();
		
		int ver = t.second;
		if (st[ver])continue;
		st[ver] = true;

		for (int i = 0; i < vec[ver].size(); ++i) {
			int j = vec[ver][i].second;
			int w = vec[ver][i].first;
			if (dist[j] > dist[ver] + w) {
				dist[j] = dist[ver] + w;
				heap.push({ dist[j],j });
			}
		}
	}

}

int dfs(int u, int start, int distance) {
	if (u == 6)return distance;

	int res = 0x3f3f3f3f;

	for (int i = 1; i <= 5; ++i) {
		int next_ = source[i]; //下一个点的编号
		if (!st[i]) {
			st[i] = true;
			res = min(res, dfs(u + 1, i, distance + dist[start][next_]));
			st[i] = false;
		}
	}

	return res;
}

int main() {
	cin >> n >> m;
	source[0] = 1;
	for (int i = 1; i <= 5; ++i)scanf("%d", &source[i]);
	while (m--) {
		int u, v, w; scanf("%d%d%d", &u, &v, &w);
		vec[u].push_back({ w,v });
		vec[v].push_back({ w,u });
	}

	for (int i = 0; i < 6; ++i) {
		dijkstra(source[i], dist[i]);
	}
	memset(st, false, sizeof st);
	printf("%d\n", dfs(1, 0, 0));
	return 0;
}

AcWing 340. 通信线路

在郊区有 N 座通信基站，P 条 双向 电缆，第 i 条电缆连接基站 A i A_i Ai​和 B i B_i Bi​。

特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 i 条电缆需要花费 L i L_i Li​。

电话公司正在举行优惠活动。

农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第1行：三个整数N，P，K。

第2…P+1行：第 i+1 行包含三个整数 A i , B i , L i A_i,B_i,L_i Ai​,Bi​,Li​

输出格式

包含一个整数表示最少花费。

若1号基站与N号基站之间不存在路径，则输出”-1”。

数据范围

0 ≤ K < N ≤ 1000 0≤K<N≤1000 0≤K<N≤1000
1 ≤ P ≤ 10000 1≤P≤10000 1≤P≤10000
1 ≤ L i ≤ 1000000 1≤Li≤1000000 1≤Li≤1000000

思路

题意为求一条从1-n的路径上的第k+1大的边的权值的最小值

因为是求最大值的最小值 可以想到用二分做

二分第k+1大的边的权值 然后把 大于这条边的边权值设置为0 小于这条边的边权值设置为1

整个图中只有权值为0/1的边 所以可以用双端队列广搜做

当 d i s t [ n ] > k dist[n] > k dist[n]>k时 说明mid的值偏小

当 d i s t [ n ] < = k dist[n] <= k dist[n]<=k时 说明mid的值可能为答案或者偏大

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
const int N = 1010;

int n, m, k;
vector<PII>vec[N];
deque<int>q;
bool st[N];
int dist[N];

bool check(int bound) {
	memset(st, false, sizeof st);
	memset(dist, 0x3f, sizeof dist);

	q.push_back(1);
	dist[1] = 0;

	while (!q.empty()) {
		auto t = q.front();
		q.pop_front();
		if (st[t])continue;
		st[t] = true;

		for(int i = 0 ;i < vec[t].size();++i){
			int j = vec[t][i].second;
			int v = vec[t][i].first > bound;
			if (dist[j] > dist[t] + v) {
				dist[j] = dist[t] + v;
				if (!v) q.push_front(j);
				else q.push_back(j);
			}
		}
	}

	return dist[n] <= k;
}

int main() {
	cin >> n >> m >> k;
	while (m--) {
		int u, v, w; cin >> u >> v >> w;
		vec[u].push_back({ w,v });
		vec[v].push_back({ w,u });
	}

	int l = 0, r = 1e6 + 1;
	while (l < r) {
		int mid = l + r >> 1;
		if (check(mid))r = mid;
		else l = mid + 1;
	}

	if (r == 1e6 + 1)r = -1;
	cout << r << endl;

	return 0;
}

AcWing 342. 道路与航线

农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到T个城镇，编号为1~T。

这些城镇之间通过R条道路 (编号为1到R) 和P条航线 (编号为1到P) 连接。

每条道路 i 或者航线 i 连接城镇 A i A_i Ai​到 B i B_i Bi​，花费为 C i C_i Ci​。

对于道路， 0 ≤ C i ≤ 10 , 000 0≤C_i≤10,000 0≤Ci​≤10,000;然而航线的花费很神奇，花费Ci可能是负数( − 10 , 000 ≤ C i ≤ 10 , 000 −10,000≤C_i≤10,000 −10,000≤Ci​≤10,000)。

道路是双向的，可以从 A i A_i Ai​到 B i B_i Bi​，也可以从 B i B_i Bi​到 A i A_i Ai​，花费都是 C i C_i Ci​。

然而航线与之不同，只可以从 A i A_i Ai​到 B i B_i Bi​。

事实上，由于最近*太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从 A i A_i Ai​到 B i B_i Bi​，那么保证不可能通过一些道路和航线从 B i B_i Bi​回到 A i A_i Ai​。

由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇S把奶牛送到每个城镇的最便宜的方案。

输入格式

第一行包含四个整数T,R,P,S。

接下来R行，每行包含三个整数（表示一个道路） A i , B i , C i A_i,B_i,C_i Ai​,Bi​,Ci​

接下来P行，每行包含三个整数（表示一条航线） A i , B i , C i A_i,B_i,C_i Ai​,Bi​,Ci​

输出格式

第1…T行：第 i 行输出从 S 到达城镇 i 的最小花费，如果不存在，则输出“NO PATH”。

数据范围

1 ≤ T ≤ 25000 1≤T≤25000 1≤T≤25000
1 ≤ R , P ≤ 50000 1≤R,P≤50000 1≤R,P≤50000
1 ≤ A i , B i , S ≤ T 1≤A_i,B_i,S≤T 1≤Ai​,Bi​,S≤T

思路

d i j k s t r a + t o p s o r t dijkstra + topsort dijkstra+topsort

没有负权边的图可以用 D i j k s t r a Dijkstra Dijkstra 有向无环图不管边权正负都可以用 S P F A SPFA SPFA

1.先输入所有双向道路 d f s dfs dfs出所有连通块 计算两个数组： i d [ ] id[] id[]存储每个点属于哪个连通块；$vectorblock[] $存储每个连通块里有哪些点；

2.输入所有航线，同时统计出每个连通块的入度

3.按照拓扑序依次处理每个连通块。先将所有入度为0的连通块的编号加入队列中

4.每次从队头取出一个连通块的编号 b i d bid bid

5.将该 b l o c k [ b i d ] block[bid] block[bid]中的所有点加入堆中，然后对堆中所有点跑 D i j k s t r a Dijkstra Dijkstra算法

6.每次取出堆中距离最小的点的 v e r ver ver

7.然后遍历 v e r ver ver的所有邻点 j j j。如果 i d [ v e r ] = = i d [ j ] id[ver] == id[j] id[ver]==id[j]那么如果j能被更新 将j插入堆中；如果 i d [ v e r ] ! = i d [ j ] id[ver] != id[j] id[ver]!=id[j]

则将 i d [ j ] id[j] id[j] 这个连通块的入度减1，如果减成0了，则将其插入拓扑排序的队列中

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

typedef long long LL;
typedef pair<int, int>PII;

const int N = 25010;

int n, mr, mp, S;
int id[N], dist[N], din[N];
vector<int>block[N];
vector<PII>vec[N];
bool st[N];
int bcnt;
queue<int>q;

void dijkstra(int bid) {
	priority_queue<PII, vector<PII>, greater<PII>>heap;

	for (int i = 0; i < block[bid].size(); ++i) {
		int j = block[bid][i];
		heap.push({ dist[j],j });
	}

	while (heap.size()) {
		auto t = heap.top();
		heap.pop();

		int ver = t.second;
		if (st[ver])continue;

		st[ver] = true;

		for (int i = 0; i < vec[ver].size(); ++i) {
			int j = vec[ver][i].second;
			int dis = vec[ver][i].first;
			if (dist[j] > dist[ver] + dis) {
				dist[j] = dist[ver] + dis;
				if (id[j] == id[ver])heap.push({ dist[j],j });
			}

			if (id[j] != id[ver] && --din[id[j]] == 0)q.push(id[j]);
		}
	}

}

void topsort() {
	memset(dist,  0x3f, sizeof dist);
	dist[S] = 0;
	for (int i = 1; i <= bcnt; ++i) {
		if (!din[i])
			q.push(i);
	}

	while (q.size()) {
		int t = q.front();
		q.pop();

		dijkstra(t);
	}
}

void dfs(int u, int bid) {
	id[u] = bid;
	block[bid].push_back(u);

	for (int i = 0; i < vec[u].size(); ++i) {
		int j = vec[u][i].second;
		if (!id[j])
			dfs(j, bid);
	}

}
int main() {
	cin >> n >> mr >> mp >> S;

	while (mr--) {
		int u, v, w;
		cin >> u >> v >> w;
		vec[u].push_back({ w,v });
		vec[v].push_back({ w,u });
	}

	for (int i = 1; i <= n; ++i) {
		if (!id[i])
			dfs(i, ++bcnt);
	}

	while (mp--) {
		int u, v, w;
		cin >> u >> v >> w;
		vec[u].push_back({ w,v });
		din[id[v]]++;
	}

	topsort();

	for (int i = 1; i <= n; ++i) {
		if (dist[i] > INF / 2)puts("NO PATH");
		else printf("%d\n", dist[i]);
	}

	return 0;
}

AcWing 341 最优贸易

C国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。

任意两个城市之间最多只有一条道路直接相连。

这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。

C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。

但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到C国旅游。

当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点旅费。

设C国 n 个城市的标号从 1~n，阿龙决定从1号城市出发，并最终在 n 号城市结束自己的旅行。

在旅游的过程中，任何城市可以被重复经过多次，但不要求经过所有 n 个城市。

阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。

因为阿龙主要是来C国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。

请你告诉阿龙，他最多能赚取多少旅费。

注意：本题数据有加强。

输入格式

第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。

第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。

接下来 m 行，每行有 3 个正整数，x，y，z，每两个整数之间用一个空格隔开。

如果z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果z=2，表示这条道路为城市 x 和城市 y 之间的双向道路。

输出格式

一个整数，表示答案。

数据范围

1≤n≤100000
1≤m≤500000
1≤各城市水晶球价格≤100

思路

d m i n [ k ] dmin[k] dmin[k] 表示 1 − k 1-k 1−k 价格的最小值 d m a x [ k ] dmax[k] dmax[k] 表示 k − n k-n k−n 价格的最大值

S P F A SPFA SPFA求出 d m i n dmin dmin和 d m a x dmax dmax后 遍历 1 − n 1-n 1−n 求出 d m a x [ k ] − d m i n [ k ] dmax[k] - dmin[k] dmax[k]−dmin[k] 的最大值

在求 d m i n dmin dmin和 d m a x dmax dmax时 需要建反图

用 D i j k s t r a Dijkstra Dijkstra会超时 所以用 S P F A SPFA SPFA

代码

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

const int N = 100010;
int n, m;
int w[N];
int dmin[N], dmax[N];
vector<int>vec1[N];
vector<int>vec2[N];
queue<int>q;
bool st[N];

void spfa(vector<int>vec[], int dist[], int type) {

	if (type == 0) {
		memset(dist, 0x3f, sizeof dmin);
		dist[1] = w[1];
		q.push(1);
	}
	else {
		memset(dist, 0, sizeof dmax);
		dist[n] = w[n];
		q.push(n);
	}

	while (q.size()) {
		int t = q.front();
		q.pop();

		st[t] = false;

		for (int i = 0; i < vec[t].size(); ++i) {
			int j = vec[t][i];
			if ((type == 0 && dist[j] > min(dist[t], w[j])) || (type == 1 && dist[j] < max(dist[t], w[j]))) {
				if (type == 0) dist[j] = min(dist[t], w[j]);
				else dist[j] = max(dist[t], w[j]);

				if (!st[j]) {
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)scanf("%d", &w[i]);

	while (m--) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		vec1[u].push_back(v);
		vec2[v].push_back(u);
		if (w == 2) {
			vec1[v].push_back(u);
			vec2[u].push_back(v);
		}
	}

	spfa(vec1, dmin, 0);
	spfa(vec2, dmax, 1);

	int res = -1;
	for (int i = 1; i <= n; ++i) {
		res = max(res, dmax[i] - dmin[i]);
	}

	cout << res << endl;
	return 0;

}