- 用迪杰斯特拉算法求最短路径
- 用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;}