题目描述
作为城市的紧急救援团队负责人,你将获得一张你所在国家的特殊地图。
该地图显示了一些通过道路连接的分散城市,道路是双向的。
地图上标出了每个城市的救援队数量以及每对城市之间的每条道路的长度。
当其他城市发出紧急求援信息时,你的工作是尽快带领你的士兵前往该地点,
同时,在途中尽可能多地调动救援帮手。
输入格式
第一行包含四个整数 N,表示城市数量(城市编号从 0 到 N−1),M 表示道路数量,
C1 表示你当前所在的城市编号,C2 表示发出紧急求援信息的城市编号。
第二行包含 N 个整数,其中第 i 个整数表示城市 i 的救援队数量。
接下来 M 行,每行包含三个整数 c1,c2,Li,表示城市 c1 和城市 c2 之间存在一条道路相连,
道路长度为 Li。
数据保证 C1 和 C2 之间至少存在一条路径相连。
输出格式
共一行,两个整数,第一个整数表示 C1 和 C2 之间最短路的数量,第二个整数表示走最短路的情况下,
能聚集到的救援队最大数量。
数据范围
2≤N≤500,
1≤M≤600,
1≤Li≤200,
每个城市包含的救援人员数量不超过 200。
输入样例:
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
输出样例:
2 4
算法1
解答
考虑到数据范围不大 基本都在几百以内,可以直接DFS加上剪枝即可搞定
想进一步深入学习的同学可以考虑学习图论算法
使用DFS 尝试从0点出发 到终点2的各种走法,不断更新每个城市从0点出发能够达到的最短路径。
如果当前达到X点的走法的路径比之前到达X点的走法的路径要长,那么这种走法就不需要继续尝试了,
因为按照这种走法达到后面的点肯定不是最短路径(剪枝)
if (currDis > dist[x]){return;}
如果当前达到X点的走法的路径比之前到达X点的走法的路径相等,
那么就需要记录达到该点的最短路径的个数,
path[x]++;
同时还需要更新下能收集到救援队数目
sum[x] = max(currSum,sum[x] );
C++ 代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;
const int N = 700;
const int INF = 0x3f3f3f3f;
int graph[N][N];
int teams[N];
int start = -1;
int endp = -1;
int n, m;
int path[N];
int dist[N];
int sum[N];
void dfs(int curr,int currDis, int currPath, int currSum)
{
if (currDis > dist[curr]){return;}
if (currDis < dist[curr]) {
dist[curr] = currDis;
sum[curr] = currSum;
path[curr] = 1;
}
else if (currDis == dist[curr] ) {
sum[curr] = max(currSum,sum[curr] );
path[curr]++;
}
if (curr == endp) { return; }
for (int i = 0; i < n; i++) {
if (i != curr && graph[curr][i] != INF) {
currPath++; currSum += teams[i];
currDis += graph[curr][i];
dfs(i, currDis,currPath, currSum);
currPath--; currSum-= teams[i];
currDis -= graph[curr][i];
}
}
return;
}
int main()
{
cin >> n >> m >> start >> endp;
for (int i = 0; i < n; i++) {
cin >> teams[i];
}
memset(graph,0x3f,sizeof(graph));
memset(dist, 0x3f, sizeof dist);
for (int i = 0; i < m; i++) {
int a, b, l;
cin >> a >> b >> l;
graph[a][b] = min(graph[a][b],l);
graph[b][a] = min(graph[b][a], l);
}
dfs(start,0,0, teams[start]);
cout << path[endp] << " " << sum[endp] << endl;
return 0;
}