1003 Emergency （25 分）多分量+ Spfa最短原路径

admin管理员组

文章数量:1577830

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

Output Specification:

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

 解题思路：

本题是l2-001的阉割版，不要求输出路径。其实如果要输出路径加一个Pre前缀数组就可以了，具体使用方法可以看我L2-001的题解。本题的写法是这样的：

用邻接矩阵存下整个图，然后使用Spfa算法去找最短路径（用Dijkstra也可以） 值得注意的是本题有很多干扰项夹杂在里。我们先弄懂题目要求输出什么。一是“the number of different shortest paths between C​1​​ and C​2”，输出最短路径的数量，注意这里输出的不是长度，如果一上来就看成长度就很容易出错了。第二是输出在这个最短路径上你能得到的最大增援数，简单来说就要用一个price数组专门存取经过的价值，在判断最短路径的时候加上值方可。 price[j] = price[p] + val[j];

//自己用spfa的写法没过...虽然过了样例但还是很郁闷 这题的题解是用dijkstra算法去写的 重做一遍吧
//第二次更改并审题发现其实这题第一个ANS要求的不是最短路径而是通路数量 晕
//但是第二次依然没有AC（事实证明这题使用spfa是可以做的
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500+10;
int Num[MAXN];
int Map[MAXN][MAXN];
int Dis[MAXN];
int GetSaveNumber[MAXN];
bool Vis[MAXN];
int ccount[MAXN];
const int INF = 16843009;
int N,M,C1,C2;
void Spfa(int s){
	for(int i = 0;i<N;i++){
		Dis[i] = INF;
		Vis[i] = false;
	}
	Dis[s] = 0;
	ccount[s] = 1;
	Vis[s] = true;
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int v = q.front();
		q.pop();
		Vis[v] = false;
		for(int i = 0;i<N;i++)
			if(Dis[i]>Map[v][i] + Dis[v]){
				Dis[i] = Dis[v] + Map[v][i];
				ccount[i] = ccount[v];
				GetSaveNumber[i] =Num[i]+ GetSaveNumber[v];
				if(Vis[i] == false){
					q.push(i);
					Vis[i] = true;
				}
			}else if(Dis[i]==Map[v][i] + Dis[v]){
				ccount[i] += ccount[v];
				if(GetSaveNumber[i] < GetSaveNumber[v] + Num[i])
					GetSaveNumber[i] = GetSaveNumber[v] + Num[i];
						if(Vis[i] == false){
					q.push(i);
					Vis[i] = true;
				}
			}
	}
}
int main(int argc, char const *argv[])
{

	cin>>N>>M>>C1>>C2;

	for (int i = 0; i < N; ++i)
	{
		cin>>Num[i];
	}
	memset(Map,1,sizeof(Map));
	for (int i = 0; i < M; ++i)
	{
		int u,v,p;

		cin>>u>>v>>p;
		Map[u][v] = p;
		Map[v][u] = p;
	}
	GetSaveNumber[C1] = Num[C1];
	Spfa(C1);
	cout<<ccount[C2]<<" ";
	cout<<GetSaveNumber[C2];
	return 0;
}

本文标签： 最短分量路径EmergencySpfa