Ciao, stavo cercando di fare police patrol 2 ma ottengo due testcase sbagliati (il 4 e il 20), con output non corretto. Non capisco cosa sto sbagliando e/o se non sto considerando un caso particolare.
Il mio codice:
#include <bits/stdc++.h>
using namespace std;
int N, M, L;
vector<int> C;
vector<vector<int>> grafo;
int scappa() {
queue<int> q;
vector<int>D(N, -1);
vector<bool>visited(N, false);
q.push(0);
D[0] = 0;
while (!q.empty()) {
int nodo = q.front();
q.pop();
if (visited[nodo]) {
continue;
}
visited[nodo] = true;
for (const int &son : grafo[nodo]) {
int tempo = D[nodo]+1;
if (C[tempo%L] == son) {
tempo ++;
}
if (D[son] == -1 || D[son]>tempo) {
D[son] = tempo;
q.push(son);
}
}
}
return D[N-1];
}
int main() {
// uncomment the following lines if you want to read/write from files
// ifstream cin("input.txt");
// ofstream cout("output.txt");
cin >> N >> M >> L;
grafo.resize(N+1);
C.resize(L);
vector<int> A(M), B(M);
for (int i = 0; i < M; ++i) {
cin >> A[i] >> B[i];
grafo[A[i]].push_back(B[i]);
grafo[B[i]].push_back(A[i]);
}
for (auto &x : C) cin >> x;
// insert your code here
cout << scappa() << endl; // print the result
return 0;
}
Quello che sto facendo è semplicemente una BFS, incrementando di 1 le distanze se il nodo a cui sto andando è occupato dalla polizia.
Grazie in anticipo.