Police Investigation 5 (0/100)

Aiuto
1

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);
}
1 Mi Piace
2

Ho modificato la lista di adiacenza da un vector<vector> ad un’ unordered_map<int, vector> e il problema della memoria non c’è più, ma comunque alcuni output sono sbagliati

3

se non sbaglio non controlli se res[N-1] è uguale a INT_MAX. mi sembra che in caso non si potesse raggiungere la destinazione bisognasse ritornare - 1. inoltre la lista di adiacenza deve avere dimensione N non M

4

grazie per aver assecondato la mia stupidità :slight_smile: