ciao, sto avendo problemi ad implementare la mia soluzione sul problema terry “caccia agli interruttori”, il mio programma dovrebbe controllare tutti i percorsi più veloci da un interruttore di tipo 1 (che si collega ad un solo nodo) ad ogni nodo, quindi trova il più grande tra essi e lo restituisce, per trovare il percorso più veloce usa il bfs.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int pmin(int par, int arr, vector<vector<int>>& g, int B) {
vector<int> d(B), p(B);
vector<bool> b(B);
queue<int> q;
q.push(par);
b[par] = true;
p[par] = -1;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int w : g[v]) {
if (!b[w]) {
b[w] = true;
d[w] = d[v] + 1;
p[w] = v;
q.push(w);
}
}
}
return d[arr];
}
void solve(int t) {
int N, A, B;
cin >> N >> A >> B;
vector<int> Z(A), X(B), Y(B);
vector<vector<int>> g(N);
for (int i = 0; i < A; i++) {
cin >> Z[i];
}
for (int i = 0; i < B; i++) {
cin >> X[i] >> Y[i];
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
int idx = 0, num = 0, ver;
for (int i = 0; i < A; i++) {
for (int j = 0; j < B; j++) {
ver = pmin(Z[i], j, g, B);
if (ver > num) {
idx = j;
num = ver;
}
}
}
cout << "Case #" << t << ": " << idx << " " << num+1 << "\n";
}
int main() {
// se preferisci leggere e scrivere da file
// ti basta decommentare le seguenti due righe:
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
solve(t);
}
return 0;
}