Salve ragazzi, stavo provando a risolvere Police Investigation 5 ma riesco solo a fare 10/100 per output errato, ho implementato semplicemente l’algoritmo di dijkstra con la condizione extra richiesta dal problema ma alcuni testcase me li restituisce errati. Ho modificato anche il template fornito per utilizzare le liste di adiacenza.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
int N,A,T,start,end,peso,esp;
cin>>N>>A>>T;
int visitato[N],dist[N];
vector<vector<pair<int,int>>> adj(N);
vector<vector<int>> esploso(N);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
for(int i=0;i<N;i++){
visitato[i]=0;
dist[i]=2147483647;
}
for(int i=0;i<A;i++){
cin>>start>>end>>peso>>esp;
adj[start].push_back(pair<int,int>(end,peso));
esploso[start].push_back(esp==1 ? T:2147483647);
}
pq.push(pair<int,int>(0,0));
dist[0]=0;
while(!pq.empty()){
pair<int,int> anal=pq.top();
pq.pop();
if(visitato[anal.first]==0){
visitato[anal.first]=1;
for(int i=0;i<adj[anal.first].size();i++){
pair<int,int>next=adj[anal.first][i];
if(dist[next.first]>dist[anal.first]+next.second){
if(dist[anal.first]+next.second<=esploso[anal.first][i]){
dist[next.first]=dist[anal.first]+next.second;
pq.push(pair<int,int>(next.first,dist[next.first]));
}
}
}
}
}
if(dist[N-1]==2147483647)dist[N-1]=-1;
cout<<dist[N-1];
return 0;
}