1003 Emergency

在这里插入图片描述

1、大致题意

无向图中，给出每个点的点权，每个边的边权（即两点之间距离），要使起点到终点距离最短，求最短路径数，并求出最大点权之和。

2、基本思路

单源最短路径问题。采用 Dijkstra算法。

该算法的思想为，设置数组 $d$ ，代表源点与各顶点的最短距离。经过 $n$ （点数）次遍历，每次遍历找到当前与源点 $s$ 距离最短的顶点 $u$ ，并以该顶点 $u$ 为中介点，找到其经过并未访问的结点 $v$ ，判断其能否使 $d [v]$ 更优（即 $）。本题目新增点权 w m 、最短路径数目 n u m 两个量，和 d 的处理方法类似。即：$

length[s->u]+d[u]时， $n u m [v]$ 更新为 $n u m [u]$ ， $w m [v]$ 更新为 $w m [u] + w [v]$ 。
length[s->u]+d[u]=d[v]时， $n u m [v]$ 更新为 $n u m [u] + n u m [v]$ 。而只有 $w m [u] + w [v] > w m [v]$ 时（以 $u$ 为中介使 $w m$ 更优），才更新 $w m [v]$ 。

 
3、解题过程 
3.1 最短路知识点 
一直想整理以下最短路相关的代码，今天不就来机会了吗。在写这道题前，我做了最短路的整理。 
这题就是典型的 Dijkstra算法，那么先上 Dijkstra的板子。 
3.1.1 Dijkstra板子 
#include
#include
#include
using namespace std;
const long long inf=0x7fffffff;;
int n,m,s,cnt;
int head[101000],vis[101000],dis[101000];

struct Edge
{
	int v,w,next;
} edge[501000];

void addEdge(int u, int v,int w)
{
	edge[++cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
}

struct node
{
	int dis;
	int pos;
	bool operator <( const node &x )const
	{
		return x.dis < dis;
	}
};
priority_queue<node>q;
void dijkstra()
{
	for(int i=1; i<=n; i++)
	{
		dis[i]=inf;
		vis[i]=0;
	}
	q.push((node)
	{
		0,s
	});
	dis[s]=0;
	while(!q.empty())
	{
		node u=q.top();
		q.pop();
		int pos=u.pos;
		if(vis[pos])
			continue;
		vis[pos]=1;
		for(int i=head[pos]; i; i=edge[i].next)
		{
			int v=edge[i].v;
			if(dis[v]>dis[pos]+edge[i].w)
			{
				dis[v]=dis[pos]+edge[i].w;
				if(!vis[v])
					q.push((node)
				{
					dis[v],v
				});
			}
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&s);
	int u,v,w;
	cnt=0;
	for(int i=0; i<m; i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		addEdge(u,v,w);
	}
	dijkstra();
	for(int i=1; i<=n; i++)
	{
		cout<<dis[i]<<" ";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84 
3.1.2 SPFA板子 
#include
const long long inf=2147483647;
const int maxn=10005;
const int maxm=500005;
using namespace std;
int n,m,s,num_edge=0;
int dis[maxn],vis[maxn],head[maxm];
struct Edge
{
	int next,to,dis;
} edge[maxm]; //结构体表示静态邻接表
void addedge(int from,int to,int dis) //邻接表建图
{
	//以下是数据结构书上的标准代码，不懂翻书看解释
	edge[++num_edge].next=head[from]; //链式存储下一条出边
	edge[num_edge].to=to; //当前节点编号
	edge[num_edge].dis=dis; //本条边的距离
	head[from]=num_edge; //记录下一次的出边情况
}
void spfa()
{
	queue<int> q; //spfa用队列，这里用了STL的标准队列
	for(int i=1; i<=n; i++)
	{
		dis[i]=inf; //带权图初始化
		vis[i]=0; //记录点i是否在队列中，同dijkstra算法中的visited数组
	}
	q.push(s);
	dis[s]=0;
	vis[s]=1; //第一个顶点入队，进行标记
	while(!q.empty())
	{
		int u=q.front(); //取出队首
		q.pop();
		vis[u]=0; //出队标记
		for(int i=head[u]; i; i=edge[i].next) //邻接表遍历，不多解释了（也可用vector代替）
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].dis) //如果有最短路就更改
			{
				dis[v]=dis[u]+edge[i].dis;
				if(vis[v]==0) //未入队则入队
				{
					vis[v]=1; //标记入队
					q.push(v);
				}
			}
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1; i<=m; i++)
	{
		int f,g,w;
		cin>>f>>g>>w;
		addedge(f,g,w); //建图，有向图连一次边就可以了
	}
	spfa(); //开始跑spfa
	for(int i=1; i<=n; i++)
		if(s==i) cout<<0<<" "; //如果是回到自己，直接输出0
		else cout<<dis[i]<<" "; //否则打印最短距离
	return 0;
} //结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65 
3.1.3 Floyd板子 
void Floyd() { //用FLoyd算法求有向网G中各对顶点和j之间的最短路径
	for(int i=0; i<n; i++) { // 初始化
		for(int j=0; j<n; j++) {
			if(i==j) {
				dist[i][j]=0;//自已到自己最短距离为0
			} else {
				dist[i][j]=G[i][j];
			}
			if(dist[i][j]<INF&&i!=j) {
				p[i][j]=i; // 如果i和j之间有边，则将j的前驱置为i
			} else {
				p[i][j]=-1; //如果i和j之间无边，则将j的前驱置为-1
			}

		}
		for(int k=0; k<n; k++) {
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					if(dist[i][k]+dist[k][j]<dist[i][j]) { //从i经k到j的- -条路径更短
						dist[i][j]=dist[i][k]+dist[k][j]; //更新dist[i][j]
						p[i][j]=p[k][j]; //更改的前驱
					}
				}
			}
		}
	}
}

void DisplayPath(int s,int t) { //输出s到t的最短路径
	if(p[s][t]!=-1) {
		DisplayPath(s,p[s][t]);
		cout<<p[s][t]<<"-->";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 
3.2 AC 代码 
#include 
#include 
#include 
using namespace std;

struct node {
	int v, dis; //目标顶点和边权
};
const int maxv = 510, INF = 1000000000;
vector<node> Adj[maxv];
int d[maxv]; 	//源点到各顶点最短路径长度
int num[maxv]; 	//最短路径条数
int wm[maxv]; 	//最多救援队数
int w[maxv]; 	//各点救援队数
bool vis[maxv] = {false};
int n, m; 		//城市数 路径数
int s, e; 		//起点和终点

void Dijkstra(int s) {
	fill(d, d + maxv, INF);
	fill(num, num + maxv, 0);
	fill(wm, wm + maxv, 0);
	d[s] = 0;
	num[s] = 1;
	wm[s] = w[s];
	for(int i = 0; i < n; i++) {
		int u = -1, min = INF;
		for(int j = 0; j < n; j++) { //找到最小d[u]
			if(vis[j] == false && d[j] < min) {
				u = j;
				min = d[u];
			}
		}
		if(u == -1) return;
		vis[u] = true;
		for(int j = 0; j < Adj[u].size(); j++) {
			int v = Adj[u][j].v; //u能到达的顶点
			if(vis[v] == false) {
				if(d[v] > d[u] + Adj[u][j].dis) {
					//以u为中介点使d[v]更优
					d[v] = d[u] + Adj[u][j].dis;
					num[v] = num[u];
					wm[v] = wm[u] + w[v];
				} else if(d[v] == d[u] + Adj[u][j].dis) {
					num[v] += num[u];
					if(wm[v] < wm[u] + w[v])
						wm[v] = wm[u] + w[v];
				}
			}
		}
	}
}

int main() {
	cin>>n>>m>>s>>e;
	for(int i = 0; i < n; i++)
		cin>>w[i];
	int c1, c2, l;
	node tmp;
	for(int i = 0; i < m; i++) {
		// 注意：无向图，两个方向都要输入
		cin>>c1>>c2>>l;
		tmp.v = c2;
		tmp.dis = l;
		Adj[c1].push_back(tmp);
		tmp.v = c1;
		Adj[c2].push_back(tmp);
	}
	Dijkstra(s);
	cout<<num[e]<<" "<<wm[e];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72



                

                    相关阅读:

                    
谷粒商城（一）                            

Redis的持久化机制和配置                            

Inter校企合作 淡水质量预测                            

Redis - 时间序列数据类型的保存方案和消息队列实现                            

HC32 IIC/I2C读写                            

【Redis 进阶】Redis 典型应用 —— 缓存（cache）                            

（C++版本）ros2发布者节点publisher示例源代码（改良版）                            

jenkins原理篇——成员权限管理                            

在 M1 芯片 Mac 上使用 Homebrew                            

大数据之hadoop入门                            

                    
                
                
                    原文地址：https://blog.csdn.net/qq_46371399/article/details/126342709



        
            
                
                    最新文章
                
                
                    
攻防演习之三天拿下官网站群                            

数据安全治理学习——前期安全规划和安全管理体系建设                            

企业安全 | 企业内一次钓鱼演练准备过程                            

内网渗透测试 | Kerberos协议及其部分攻击手法                            

0day的产生 | 不懂代码的"代码审计"                            

安装scrcpy-client模块av模块异常，环境问题解决方案                            

leetcode hot100【LeetCode 279. 完全平方数】java实现                            

OpenWrt下安装Mosquitto                            

AnatoMask论文汇总                            

【AI日记】24.11.01 LangChain、openai api和github copilot                            

                    
                
            

            
                
                    热门文章
                
                
                    
十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧！！！                            

奉劝各位学弟学妹们，该打造你的技术影响力了！                            

五年了，我在 CSDN 的两个一百万。                            

Java俄罗斯方块，老程序员花了一个周末，连接中学年代！                            

面试官都震惊，你这网络基础可以啊！                            

你真的会用百度吗？我不信 — 那些不为人知的搜索引擎语法                            

心情不好的时候，用 Python 画棵樱花树送给自己吧                            

通宵一晚做出来的一款类似CS的第一人称射击游戏Demo！原来做游戏也不是很难，连憨憨学妹都学会了！                            

13 万字 C 语言从入门到精通保姆级教程2021 年版                            

10行代码集2000张美女图，Python爬虫120例，再上征途

1003 Emergency

1003 Emergency

1、大致题意

2、基本思路

3、解题过程

3.1 最短路知识点

3.1.1 `Dijkstra`板子

3.1.2 `SPFA`板子

3.1.3 `Floyd`板子

3.2 AC 代码