1003 Emergency（dijkstra+dfs）

短命女 2024-04-08 08:41 44阅读 0赞

## 1003 Emergency（Dijkstra+dfs） ##

### 0、题目 ###

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

#### Input Specification: ####

Each input file contains one test case. For each test case, the first line contains 4 positive integers:  N N N ( ≤ 500 ≤500 ≤500) - the number of cities (and the cities are numbered from  0 0 0 to  N − 1 N−1 N−1),  M M M \- the number of roads,  C 1 C\_1 C1 and  C 2 C\_2 C2 \- the cities that you are currently in and that you must save, respectively. The next line contains  N N N integers, where the i-th integer is the number of rescue teams in the i-th city. Then  M M M lines follow, each describes a road with three integers  c 1 c\_1 c1,  c 2 c\_2 c2 and  L L L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from  C 1 C\_1 C1 to  C 2 C\_2 C2.

#### Output Specification: ####

For each test case, print in one line two numbers: the number of different shortest paths between  C 1 C\_1 C1 and  C 2 C\_2 C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

#### Sample Input: ####

5 6 0 2
    1 2 1 5 3
    0 1 1
    0 2 2
    0 3 1
    1 2 1
    2 4 1
    3 4 1

![在这里插入图片描述][e14ae5cccfb748569e8434a869975330.png]

#### Sample Output: ####

2 4

### 1、大致题意 ###

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

### 2、基本思路 ###

安利一个[在线绘制图的网站][Link 1]

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

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

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

### 3、解题过程 ###

#### 3.1 最短路知识点 ####

一直想整理以下最短路相关的代码，今天不就来机会了吗，这题就是典型的 `Dijkstra`算法，那么先上 `Dijkstra`的板子。

##### 3.1.1 `Dijkstra`板子 #####

#include<iostream>
    #include<algorithm>
    #include<queue>
    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;
    }

##### 3.1.2 `SPFA`板子 #####

#include<bits/stdc++.h>
    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;
    } //结束

##### 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]<<"-->";
    	}
    }

#### 3.2 AC 代码 ####

#include<iostream>
    #include<algorithm>
    #include<queue>
    #include<cstring>
    using namespace std;
    const long long inf=0x7fffffff;;
    int n,m,s,e,cnt,a[101000],end_n,end_num;
    int head[101000],vis[101000],dis[101000];
    vector<int> pre[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(int s) {
        
    	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) {
        
    				if(dis[v]>dis[pos]+edge[i].w) {
        
    					pre[v].clear();
    					dis[v]=dis[pos]+edge[i].w;
    				}
    				pre[v].push_back(pos);
    				if(!vis[v]) {
        
    					q.push((node){
        dis[v],v});
    				}
    			}
    		}
    	}
    }
    
    
    void dfs(int pos,int num) {
        
    	num+=a[pos];
    	if(pos==s) {
        
    		end_n++;
    		if(num>end_num) {
        
    			end_num=num;
    		}
    		return;
    	}
    	for(int i=0; i<pre[pos].size(); i++) {
        
    		dfs(pre[pos][i],num);
    	}
    }
    
    int main() {
        
    	scanf("%d%d%d%d",&n,&m,&s,&e);
    	memset(edge,0,sizeof(edge));
    	for(int i=0; i<n; i++) {
        
    		scanf("%d",&a[i]);
    	}
    	
    	int u,v,w;
    	cnt=0;
    	for(int i=0; i<m; i++) {
        
    		scanf("%d%d%d",&u,&v,&w);
    		addEdge(u,v,w);
    		addEdge(v,u,w);
    	}
    	dijkstra(s);
    
    	end_n=0,end_num=0;
    	dfs(e,0);
    
    	cout<<end_n<<" "<<end_num;
    	return 0;
    }

![在这里插入图片描述][f32ee733821f4a51b4ff46b7ac39aad8.png]

[e14ae5cccfb748569e8434a869975330.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c6f2475410a142c784eb0b04ce358942.png
[Link 1]: https://csacademy.com/app/graph_editor/
[f32ee733821f4a51b4ff46b7ac39aad8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/b168eb3c7f1847189558927eeff69be2.png