1003 Emergency (25分) DFS 深度优先遍历

admin管理员组

文章数量:1577823

1003 Emergency (25分)

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, C
​1​​and C​2​​- 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, c​2
​​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 C​2.

Output Specification:

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

心得

这个题使用的时DFS深度优先遍历。主要是对图的处理，对图的处理可以用vector<vector<>>int path(500)这种来储存，储存他的后续节点。要使用一个标记数组，标记当前点是否储存过。

该题DFS就是初始节点开始。判断时否到终止节点。没有到终止节点就对vector里面的继续遍历。当遍历过一次时要对上一轮的标记清除，防止影响下一个遍历。
该题没有剪枝，其实可以剪枝的。

错误

忘记清除做多医生数量。当minPath最短长度替换时，最多医生数量也要清零。

int cityNum, roadNum, C1, C2;
int docNum[500] = { 0 };
vector<vector<int>> path(500);
int len[500][500];
int maxDoc = 0;//最多的医生
int minPath = 0; //最短路的数量
int minLength = 1<<30; //最短的长度
int havaGo[500] = {0};//0代表没走
void DFS(int begin,int nowLength,int nowDocNum) {
	if (nowLength > minLength) return;
	if (begin == C2) {
		if (nowLength < minLength) {
			minLength = nowLength;
			minPath = 1;
			maxDoc = nowDocNum;
		}
		else if (nowLength == minLength) {
			minPath += 1;
			if (nowDocNum > maxDoc) {
				maxDoc = nowDocNum;
			}
		}
		
		return;
	}  
	for (int i = 0; i < path[begin].size(); i++)
	{ 
		if (havaGo[path[begin][i]] == 1) continue;

		havaGo[path[begin][i]] = 1;
		DFS(path[begin][i],nowLength+len[begin][path[begin][i]], nowDocNum+docNum[path[begin][i]]);
		havaGo[path[begin][i]] = 0;
	}
}

int main() {
	
	cin >> cityNum >> roadNum >> C1 >> C2;
	for (int i = 0; i < 500; i++)
		for (int j = 0; j < 500; j++)
			len[i][j] = -1;

	for (int i = 0; i< cityNum; i++)
		cin >> docNum[i];
	for (int i = 0; i < roadNum; i++)
	{
		int C1, C2, length;
		cin >> C1 >> C2 >> length;
		path[C1].push_back(C2);
		path[C2].push_back(C1);
		len[C1][C2] = length;
		len[C2][C1] = length;
	}
	havaGo[C1] = 1;
	DFS(C1,0, docNum[C1]);

	cout << minPath <<" "<< maxDoc;

	return 0;
}

本文标签： 遍历深度EmergencyDFS