和PAT-甲1018類似的題，用dns或者dij求解
#include<iostream>#include<vector>#define INF 0x3f3f3f#define MAX_V 502int N, M, C1, C2;int teams[MAX_V];int arc[MAX_V][MAX_V] = {0};int num=1, max_teams;int temp_d=0, min_d = INF,temp_teams=0;using namespace std;bool visited[MAX_V];void bfs(int index){ if (temp_d > min_d) { return; } if (index == C2) { if (temp_d < min_d) { min_d = temp_d; num = 1; max_teams = temp_teams; } else if (temp_d == min_d) { num++; max_teams = max_teams > temp_teams ? max_teams : temp_teams; } } for (int t = 0;t < N;t++) { if (visited[t] == false && arc[index][t] != 0) { temp_d +=arc[index][t]; temp_teams += teams[t]; visited[t] = true; bfs(t); visited[t] = false; temp_d -= arc[index][t]; temp_teams -= teams[t]; } }}int main(){ cin >> N >> M >> C1 >> C2; for (int t = 0;t < N;t++) { cin >> teams[t]; visited[t] = false; } for (int t = 0;t < M;t++) { int i, j, k; cin >> i >> j >> k; arc[i][j] = arc[j][i] = k; } temp_teams += teams[C1]; visited[C1] = true; bfs(C1); cout << num << " " << max_teams << endl;}新聞熱點
疑難解答
