PTA甲级 1003 Emergency (25分) Dijkstra+DFS

强烈推荐,刷PTA的朋友都认识一下柳神–PTA解法大佬

本文由参考于柳神博客写成

柳神的CSDN博客,这个可以搜索文章

柳神的个人博客,这个没有广告,但是不能搜索

还有就是非常非常有用的 算法笔记 全名是

算法笔记  上级训练实战指南		//这本都是PTA的题解
算法笔记

PS 今天也要加油鸭

题目原文

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 (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and 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 C1 to C2.

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between C1 and 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

Sample Output:

2 4

生词如下:

PS:可能是因为我原来写过的原因,这题我是看的懂的.

但是问题是,许多词的意思.其实我并不知道.这样考试肯定还是不行的

scattered 疏散

题目大意:

最短路径,然后在多条路径下要算最大的点权之和

思路如下:

我直接套的算法笔记的公式

矩阵+标准 Dijkstra模板

#include<iostream>
using namespace std;
const int Max = 510;
const int INF = 1000000000;
int n, m, c1, c2,G[Max][Max],weight[Max],t1,t2,t3,d[Max],w[Max],num[Max];
//d就是最短c1到每个点的最短路径,w就是c1到每个点的最多救援人数.num就是c1到每个人的最短路径长度
bool vis[Max] = { false };
void Dijkstra(int s) {
	fill(d, d + Max, INF);			
	d[s] = 0;			//自己到自己的长度为0
	w[s] = weight[s];	//自己一共有weight[s]个救援队
	num[s] = 1;			//自己到自己一共就有一条路
	for (int i = 0; i < n; ++i) {
		int u = -1, MIN = INF;
		for (int j = 0; j < n; ++j) {		//在所有剩下的节点中找d最小的
			if (!vis[j] && d[j] < MIN) {
				MIN = d[j];
				u = j;
			}
		}	
		if (u == -1)	return;				//判断有没有从u到别的地方.有没有别的联通节点
		vis[u] = true;
		for (int v = 0; v < n; ++v) {
			if (!vis[v] && G[u][v] != INF) {	//只有G[u][v]是存在的.而且v点没有访问过,程序才可以进行
				if (d[u] + G[u][v] < d[v]) {//发现了新的最小路径
					d[v] = d[u] + G[u][v];	//更新这个点的最小路径
					num[v] = num[u];//新的点的最大路径数,等于上一个点的路径数
					w[v] = weight[v] + w[u];//一共有的救援队的数量就是前面的数量之和加上这个点的救援对的数量
				}
				else if (d[u] + G[u][v] == d[v]) {//最小路径重叠
					//但这条路径的救援队的数量大于原来的时候,更新救援队数量
					if (weight[v] + w[u] > w[v])	w[v] = weight[v] + w[u];
					num[v] += num[u];
					//路径是一定要加上的.
				}
			}
		}
	}
	return;
}
int main(void) {
	scanf("%d%d%d%d", &n, &m, &c1, &c2);					//读入n,m,c1,c2
	for (int i = 0; i < n; ++i)	scanf("%d", &weight[i]);	//weight代表点权
	fill(G[0], G[0] + Max * Max, INF);						//把所有的图初始化为0
	for (int i = 0; i < m; ++i) {		
		scanf("%d%d%d", &t1, &t2, &t3);	
		G[t1][t2] = t3;
		G[t2][t1] = t3;
	}														//读入我们已知的边
	Dijkstra(c1);
	printf("%d %d\n", num[c2], w[c2]);
	return 0;
}

下面是是Dijkstra+DFS的改进版

#include<iostream>
#include<vector>
const int Max = 510;
const int INF = 1000000000;
using namespace std;
int n, m, c1, c2,weight[Max],G[Max][Max],t1,t2,t3,d[Max],st,optvalue=INF,num[Max],w[Max];
//optvalue是边权
int optvalue_W = -1;
vector<int> pre[Max];
vector<int> path, tempPath;
bool vis[Max] = { false };
void Dijkstra(int s) {
	fill(d, d + Max, INF);
	d[s] = 0;
	num[s] = 1;
	w[s] = weight[s];
	for (int i = 0; i < n; ++i) {
		int u = -1, MIN = INF;
		for (int j = 0; j < n; ++j) {
			if (!vis[j] && d[j] < MIN) {
				u = j;
				MIN = d[j];
			}
		}
		if (u == -1)return;
		vis[u] = true;
		for (int v = 0; v < n; ++v) {
			if (!vis[v] && G[u][v] != INF) {
				if (d[u] + G[u][v] < d[v]) {
					d[v] = d[u] + G[u][v];
					pre[v].clear();
					pre[v].push_back(u);
					num[v] = num[u];
				}
				else if (d[u] + G[u][v] == d[v]) {
					pre[v].push_back(u);
					num[v] += num[u];
				}
			}
		}
	}
}
void DFS(int v) {		//求点权之和的
	if (v == c1) {
		tempPath.push_back(v);
		int value = 0;	//边权之和
		for (int i = tempPath.size() - 1; i >=0; --i) {
			int id = tempPath[i];
			value += weight[id];
		}
		if (value > optvalue_W) {
			optvalue_W = value;
			path = tempPath;
		}
		tempPath.pop_back();
		return;
	}
	//递归式
	tempPath.push_back(v);
	for (int i = 0; i < pre[v].size(); ++i) DFS(pre[v][i]);
	tempPath.pop_back();									//遍历完所有前驱结点.将当前结点v
	//删除
}
int main(void) {
	scanf("%d%d%d%d", &n, &m, &c1, &c2);
	for (int i = 0; i < n; ++i)	scanf("%d",&weight[i]);
	fill(G[0], G[0] + Max * Max, INF);
	for (int i = 0; i < m; ++i) {
		scanf("%d%d%d", &t1, &t2, &t3);
		G[t1][t2] = t3; G[t2][t1] = t3;
	}
	Dijkstra(c1);
	DFS(c2);
	printf("%d %d\n", num[c2], optvalue_W);
	return 0;
}

如果这篇文章对你有张帮助的话,可以用你高贵的小手给我点一个免费的赞吗

相信我，你也能变成光.

如果你有任何建议,或者是发现了我的错误,欢迎评论留言指出.