PTA天梯赛-练习集 L2-001 紧急救援(dijk + dfs)
题目给出的图不光路径有权值, 每个点也有权值,让求最短路径的个数,及最短路径中经过点的权值和最大的最优路径,
输出最短路径条数,点的最大权值和,及最优路径走法。
思路:先用dijk求出最短路径的长度minlen,在用dfs求出最优路径,中间用minlen来进行最优解剪枝。
#include <bits/stdc++.h>
using namespace std;
#define d(x) cout << (x) << endl
typedef long long ll;
const int N = 5e2 + 10;
const int INF = 0x3f3f3f3f;
int n, m, s, d;
int minlen; //最短路径长度
int cnt; //最短路径数
int ss; //最优路径长度
int maxnum; //最大救援队数量
int a[N][N]; //图
bool vis[N]; //标记数组
int ans[N]; //s到每个点的最短距离
int num[N]; //城市救援队数量
int buf[N]; //保存当前路径
int path[N]; //保存最优路径
void dijk(int u)
{
for (int i = 0; i < n; i++){
a[i][i] = 0;
ans[i] = a[u][i];
}
vis[u] = 1;
int v, pos;
for (int i = 1; i < n; i++){ //循环n-1次
v = 0; //找到 ans 中最小的
pos = INF;
for (int j = 0; j < n; j++){
if(!vis[j] && ans[j] < pos){
pos = ans[j];
v = j;
}
}
vis[v] = 1;
for (int i = 0; i < n; i++){ //更新ans数组
ans[i] = min(ans[i], ans[v] + a[v][i]);
}
}
minlen = ans[d];
}
void dfs(int u, int len, int sum, int step)
{
buf[step] = u;
if(len > minlen)
return;
if(u == d && len == minlen){ //找到最短路径
cnt++;
if(sum > maxnum){ //找到最优路径
maxnum = sum;
ss = step;
memcpy(path, buf, sizeof(buf));
}
return;
}
for (int i = 0; i < n; i++){
if(!vis[i]){
vis[i] = 1;
dfs(i, len + a[u][i], sum + num[i], step+1);
vis[i] = 0; //回溯
}
}
}
int main()
{
cin >> n >> m >> s >> d;
memset(a, INF, sizeof(a));
for (int i = 0; i < n; i++){
scanf("%d", &num[i]);
}
while (m--){
int x, y, num;
scanf("%d%d%d", &x, &y, &num);
a[x][y] = a[y][x] = min(a[x][y], num);
}
dijk(s);
memset(vis, 0, sizeof(vis));
vis[s] = 1;
dfs(s, 0, num[s], 0);
printf("%d %d\n", cnt, maxnum);
for (int i = 0; i <= ss; i++){
printf("%d%c", path[i], " \n"[i == ss]);
}
return 0;
}