- 用迪杰斯特拉算法求最短路径
- 用before的vector数组记录当前的结点的所有上一个结点,通过这种方式记录下一个以出发结点和终点为起点和终点,用最短路径构成的拓扑图(所有以起点和终点的最短路径长度相等)
- 用深度优先算法遍历各个拓扑图并获得各条路上的救火队数目,并计算最短路径的条数。
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 505;
const int inf = 1000000000;
int teamNum[maxn];
int road[maxn][maxn];
int visit[maxn], cost[maxn];
vector<int> before[maxn];
vector<int> q, remenber;
int maxTeam = 0, projectNum = 0;
int start;
void DFS(int aim) {
if (aim == start) {
projectNum++;
int totalTeam = 0;
//printf("\n"); //
for (int i = 0; i < q.size(); i++) {
totalTeam += teamNum[q[i]];
// printf("%d ", q[i]);
}
if (totalTeam > maxTeam) {
maxTeam = totalTeam;
remenber = q;
}
return;
}
for (int i = 0; i < before[aim].size(); i++) {
q.push_back(before[aim][i]);
DFS(before[aim][i]);
q.pop_back();
}
return;
}
int main() {
int N, M, aim;
scanf("%d %d %d %d", &N, &M, &start, &aim);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j) road[i][i] = 0;
else road[i][j] = inf;
}
}
for (int i = 0; i < N; i++) {
visit[i] = inf;
cost[i] = inf;
}
for (int i = 0; i < N; i++) {
scanf("%d", &teamNum[i]);
}
int c1, c2, length;
for (int i = 0; i < M; i++) {
scanf("%d %d %d", &c1, &c2, &length);
road[c1][c2] = length;
road[c2][c1] = length;
}
visit[start] = 0;
int smaller = start, m = inf;
bool done = false;
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
if (i == smaller) continue;
if (road[smaller][i] + visit[smaller] < cost[i]) {
cost[i] = road[smaller][i] + visit[smaller];
before[i].clear();
before[i].push_back(smaller);
}
else if (road[smaller][i] + visit[smaller] == cost[i]) {
before[i].push_back(smaller);
}
}
if (done == true) break;
smaller = -1, m = inf;
for (int i = 0; i < N; i++) {
if (visit[i] == inf && cost[i] < m) {
m = cost[i];
smaller = i;
}
}
visit[smaller] = cost[smaller];
if (smaller == aim) done = true;
}
q.push_back(aim);
DFS(aim);
printf("%d %d", projectNum, maxTeam);
return 0;
}