"Execution killed with signal 11" su Dijkstra

Salve, chiedo nuovamente di ottenere chiarezza circa un esercizio che ho provato a risolvere (dijkstra). Ho già costruito il codice e l’algoritmo, ed in locale sembrerebbe funzionare perfettamente, mentre sfortunatamente non sembrerebbe essere così quando la piattaforma corregge l’esercizio.

Il codice è il seguente:

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

int main() {
  int N, M;
  int src, dest, weight;
  int departure, arrival, current;

  cin >> N >> M;
  cin >> departure >> arrival;

  departure--, arrival--;

  vector<map<int, int>> graph(N);
  map<int, int> weights;
  queue<int> q;
  set<int> v;

  while (M--) {
    cin >> src >> dest >> weight;
    graph[src - 1][dest - 1] = weight;
    graph[dest - 1][src - 1] = weight;
  }

  weights[departure] = 0;
  q.push(departure);

  while (q.size() > 0) {
    current = q.front();
    q.pop();
    v.insert(current);

    for (auto e : graph[current]) {
      if (v.count(e.first) != 1) q.push(e.first);

      if (weights.count(e.first) == 0)
        weights[e.first] = e.second + weights[current];
      else
        weights[e.first] = min(weights[e.first], e.second + weights[current]);
    }
  }

  cout << weights[arrival] << endl;
  return 0;
}

Vi ringrazio tutti in anticipo e chiedo umilmente scusa per il disturbo.

Il problema richiede l’input e output da file. Se non ricordo male il grafo non è bidirezionale.

1 Mi Piace

Come ha detto @zJack1342 il grafo non è bidirezionale devi leggere/scrivere da/su file di testo, basta che aggiungi:

  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);

Inoltre devi utilizzare i long long per memorizzare le distanze, altrimenti hai overflow.
Aggiustate queste 3 cose il tuo codice prenderà 70/100, soprattutto perché la tua implementazione di dijkstra è molto diversa da quella “classica e corretta”.

Innanzitutto il grafo lo devi memorizzare tramite le liste di adiacenza, ossia per ogni nodo x hai una lista che contiene tutti i nodi raggiungibili da x ed eventualmente la loro distanza. E poi il ragionamento di Dijkstra è il seguente.

  • Hai una priority_queue che contiene {distanza, nodo} ordinata in ordine crescente per distanza.
  • Hai un array che ti dice se hai già visitato un nodo(può essere un bool oppure per velocizzare l’algoritmo puoi salvarti per ogni nodo la distanza minore dal nodo sorgente). Per visitato si intende quando il nodo è il primo (ossia quello con distanza minore) nella pq, quando accade ciò per la prima volta significa che hai trovato il percorso minimo per quel nodo.
  • Inserisci il nodo iniziale con distanza 0 nella pq.
  • Fino a quando la pq non è vuota:
    • Prendi il primo nodo dalla pq.
    • Se è il nodo finale allora ritorna la distanza di quel nodo.
    • Controlla che non sia già stato visitato.
    • Se non lo è aggiungi nella pq con le relative distanze, i nodi che non sono già stati visitati raggiungibili dal nodo che hai appena estratto.

So che è uno spoiler gigante ma effettivamente ritengo più costruttivo mostrare un buon codice per Dijkstra, anche perché è un problema classicissimo quindi è meglio saperlo scrivere bene.
Questo è un mio template per risolvere Dijkstra:

template<typename T> T dijkstra(int N, int start, int end, vector<vector<pair<int,T>>> &graph){
	vector<T> dist(N,-1);
	priority_queue<pair<T,int>,vector<pair<T,int>>,greater<pair<int,T>>> pq;
	dist[start]=0;
	pq.push({0,start});
	while(!pq.empty()){
		auto [d,node]=pq.top();
		if(node==end)
			return d; 
		pq.pop();
		for(auto next:graph[node])
			if(dist[next.first]==-1 || dist[next.first]>d+next.second){
				dist[next.first]=d+next.second;
				pq.push({dist[next.first],next.first});
			}
	}
	return -1;
}

Ha come parametri il numero di nodi( da 0 a N-1), il nodo sorgente, quello destinazione, e poi graph dove graph[i] è una lista che contiene dei pair<nodo,distanza>, ossia i nodi raggiungibili dai i e la loro distanza dal nodo i.

Se il nodo destinazione non è raggiungibile da quello sorgente allora la funzione restituisce -1.

Inoltre invece di usare un array booleano per sapere se un nodo x è stato visitato o meno utilizza un vettore che indica la minima distanza di x dal nodo sorgente che è stata trovata sino ad ora. Il vantaggio è che mentre con l’array booleano puoi fare vis[node]=true; solo nel momento in cui arriva in cima alla pq, con la distanza tu puoi settarla direttamente nel momento in cui la inserisci nella pq, e questo implica che eviti che succeda qualcosa come: nella pq hai {dist=x, nodo=k} ma non è ancora in cima alla pq e quindi inserisci anche {dist=y (y>=x), nodo=k} quando non serve a nulla.

1 Mi Piace

Ringrazio vivamente entrambi per l’aiuto.


Ho riguardato autonomamente come funziona l’algoritmo di Dijkstra, evidentemente me lo ricordavo davvero in modo pessimo.

Ti ringrazio nuovamente: ho dato un’occhiata al codice e mi ha chiarito alcune idee, nonostante le poche intuizioni e chiarezze che avevo in giro per la testa siano svanite (per esempio, non so ancora spiegarmi perché utilizzare una priority_queue invece che una queue normale, nonostante qualcosina adesso riesca un po’ ad intravederla); tenterò di recuperarle facendo più esercizi dedicati o cercando di dimostrare il medesimo algoritmo a me stesso.

Ho applicato il consiglio di non utilizzare un vettore di valori booleani, in quanto, effettivamente, non serviva ad un granché.

Ciononostante, il codice sottostante riesce a darmi solo 20/100 (primi tre testcase ed anche poi l’ultimo). Ho cambiato da int a long long, dato che in effetti vi era il pericolo overflow. Dove sto sbagliando?

#include <queue>
#include <fstream>
#include <vector>

#define int long long

using namespace std;

int32_t main() {
  int N, M;
  int src, dest, weight;
  int departure, arrival;

  ifstream cin("input.txt");
  ofstream cout("output.txt");

  cin >> N >> M;
  cin >> departure >> arrival;

  departure--, arrival--;

  vector<vector<pair<int, int>>> graph(N);
  vector<int> weights(N, -1);
  priority_queue<int, vector<pair<int, int>>, greater<pair<int, int>>> pq;

  while (M--) {
    cin >> src >> dest >> weight;
    graph[src - 1].push_back({dest - 1, weight});
    graph[dest - 1].push_back({src - 1, weight});
  }

  weights[departure] = 0;
  pq.push({0, departure});

  while (!pq.empty()) {
    auto current = pq.top();

    if (current.second == arrival) {
      cout << current.first << endl;
      return 0;
    }

    pq.pop();

    for (auto e : graph[current.second]) {
      if (weights[e.first] == -1 || weights[e.first] > e.second + current.first) {
        weights[e.first] = e.second + current.first;
        pq.push({weights[e.first], e.first});
      }
    }
  }

  return 0;
}

Ti ringrazio ancora per la grande disponibilità dimostrata.

L’errore stava qui; nel fare un po’ di prove in locale, mi ero dimenticato di impostare il grafo come unidirezionale e non bidirezionale. 100/100! Il codice corretto è dunque pubblicato.

Usando una priority_queue valuti i percorsi in base alla lora distanza, quindi sarai certo che il percorso con distanza minima per un certo nodo corrisponde alla prima volta che quel nodo compare nella priority_queue. Se ci fossero percorsi più brevi allora sarebbero già stati inseriti nella pq, e li avresti estratti prima di quello attuale.

1 Mi Piace

Ti ringrazio, vedrò di capirlo ancora meglio.