Ho letteralmente implementato un dijkstra con un controllo in più, ma in alcuni casi mi da “Execution killed (could be triggered by violating memory limits)” e in altri output scorretto, aiuto?
#include <bits/stdc++.h>
using namespace std;
struct node
{
int index;
int weight;
int explode;
};
int dijkstra(int N, int T, vector<vector<node>>&adj)
{
vector<bool>visited(N, false);
vector<int>res(N, INT_MAX);
priority_queue<pair<int, int>> min_pq;
min_pq.push({0, 0});
res[0] = 0;
while(!min_pq.empty())
{
int tmp = min_pq.top().second;
min_pq.pop();
if(visited[tmp]) continue;
visited[tmp] = true;
for(node &v : adj[tmp])
{
int i = v.index;
int w = v.weight;
int e = v.explode;
if(e == 1 && res[tmp] + w > T) continue; //esplode troppo presto
else if(res[tmp] + w < res[i])
{
res[i] = res[tmp] + w;
min_pq.push(make_pair(-res[i], i));
}
}
}
return res[N - 1];
}
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int N, M, T;
cin >> N >> M >> T;
vector<vector<node>> adj(M);
for(int i = 0; i != M; i++)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
adj[a].push_back({b, c, d});
}
cout << dijkstra(N, T, adj);
}