Buongiorno ragazzi. So che non mi si vede da un po’ ma solo adesso mi sto allenando per le Olimpiadi di Informatica nazionali (che perderò sicuramente, in quanto sto iniziando ad allenarmi solo adesso…)
Per quanto riguarda il problema del topic, il correttore non accetta il mio programma nonostante sia corretto e superi il caso d’esempio. Ho pensato che la causa fosse del newline, come molto spesso capita, ma non lo era.
Codice che ho usato:
#include <cstdio>
#include <utility>
#include <set>
#include <vector>
#include <climits>
using namespace std;
struct edge {int to, peso;};
// tratto da https://www.quora.com/What-is-the-most-simple-efficient-C++-code-for-Dijkstras-shortest-path-algorithm
int dijkstra(const vector<vector<edge>> & graph, int source, int target) {
vector<int> min_distance(graph.size(), INT_MAX);
min_distance[source] = 0;
set<pair<int, int> > active_vertices;
active_vertices.insert({0, source});
while(!active_vertices.empty()) {
int where = active_vertices.begin()->second;
if(where == target) return min_distance[target];
active_vertices.erase(active_vertices.begin());
for(auto ed: graph[where]) {
if(min_distance[ed.to] > min_distance[where] + ed.peso) {
active_vertices.erase({min_distance[ed.to], ed.to});
min_distance[ed.to] = min_distance[where] + ed.peso;
active_vertices.insert({min_distance[ed.to], ed.to});
}
}
}
return INT_MAX;
}
int main()
{
FILE* in, *out;
in = fopen("input.txt", "r");
out = fopen("output.txt", "w");
int N, archi, src, dst;
fscanf(in, "%d %d %d %d", &N, &archi, &src, &dst);
vector<vector<edge>> grafo(N+1);
for(int i = 0; i < archi; i++) {
int da, a, peso;
fscanf(in, " %d %d %d", &da, &a, &peso);
grafo[da].push_back({a, peso});
grafo[a].push_back({da, peso});
}
fprintf(out, "%d", dijkstra(grafo, src, dst));
fclose(in);
fclose(out);
return 0;
}
Ho inviato una versione non bidirezionata (semplicemente rimuovendo la riga 49) ma ancora il punteggio è 0/100. Stavolta gli errori sarebbero “Output isn’t correct” e “Execution killed by signal 11”, ma ancora non capisco. Nel mio programma non ottengo mai errori di segmentazione, né accedo a locazioni di memoria inaccessibili.
Soluzione del programma: 29 (che spero sia corretta, non ho potuto verificare manualmente né con un altro programma online perché non ne trovo online di simulatori monodirezionali).
Nessun problema rilevato da valgrind.
Mmm… i valori massimi per N, M, e il peso P sono rispettivamente 10000, 1000000, e 1000000, che stanno ampiamente nell’int (che arriva fino a oltre 2000000000).
Tuttavia, il problema dell’overflow si potrebbe in effetti presentare nel valore da stampare in output ovvero la distanza dal nodo sorgente al nodo destinazione: basta pensare a un grafo in cui hai 10000 nodi disposti in una lunga lista concatenata, e hai 10000-1 = 9999 archi che li connettono, ciascuno dei quali ha peso 1000000.
In ogni caso non credo sia questo il problema in questo caso, dato che l’esito è proprio 0/100, e l’overflow sicuramente non capiterà in tutti i casi
@erixstep una nota a margine: Dijkstra è una di quelle cose che sarebbe bene conoscere ed essere in grado di scrivere da zero, dato che nelle gare ufficiali solitamente non c’è accesso a internet
strano, ho sottoposto al correttore lo stesso identico programma di erixstep sostituendo int con long long ed ho ottenuto 100/100.
se non mi sbaglio int arriva fino a 32 000, long fino a 2000000000, e long long fino a 9000000000000000000.
credo basti long ma per sicurezza uso sempre long long
In realtà il C/C++ non specifica una dimensione precisa per short int, int, long int, long long int. Semplicemente, ti garantisce che sizeof(short int) <= sizeof(int) <= sizeof(long int) <= sizeof(long long int), se non erro. (Ah, sizeof(x) restituisce il numero di byte occupati dal tipo o dalla variabile x).
Quindi, in teoria, un compilatore potrebbe tranquillamente implementare questi tipi di dato con delle dimensioni del tutto inaspettate
In pratica, per fortuna, vale più o meno sempre questa regola:
sizeof(short int) = 2, ovvero short int permette di memorizzare fino a 32000 circa.
sizeof(int) = 4, ovvero int permette di memorizzare fino a 2000000000 circa.
sizeof(long int) = 4, ovvero long int è identico a int.
sizeof(long long int) = 8, ovvero long long int permette di memorizzare fino a 2^{63}-1.
Nell’industria (quando devi scrivere codice portabile, ovvero che si comporta allo stesso modo anche compilandolo con compilatori diversi) si cerca sempre di evitare questi tipi di dato proprio perché non danno garanzie. Si preferisce infatti includere stdint.h e usare questi tipi (che offrono garanzie!): http://www.cplusplus.com/reference/cstdint/
Verissimo, non contraddico, solo che, come ho detto ieri, ho appena iniziato. Adesso so scrivere l’algoritmo Dijkstra da 0 (e ho usato lo stesso identico algoritmo senza copiare da internet) per risolvere il problema sentieri (con esito 100/100).
@MrBrionix hai ragione, con i long long ottengo come risultato 100/100.
Devo probabilmente attribuire la causa al fatto che tutti i test case abbiano pesi molto alti.
Certo, devo dire che questa prova è un po’ “irregolare”, nel senso che mancano i canonici criteri di giudizio di ogni testcase. Cosa che senz’altro non mi piace ma che è comunque lecita (non lo fanno quelli del Valladolid, perché dovrei pretendere che OII lo faccia ogni volta? ). Ciò spiega molto.
A questo punto farei una modifica al testo consigliando di usare un long long int
Proprio quella riga ho eliminato, niente di più, niente di meno.
Magia magia, ho reinviato il codice con gli int e senza bidirezione, e adesso funziona a meraviglia.
Che fino a stamattina fosse buggato il sistema di verifiche?
Boh, io non ho cambiato nulla lato server magari fate il diff (se siete su linux/mac) tra il file che avete mandato ora e il file che avevate mandato prima, per assicurarvi che siano identici…
P.S. comunque penso che a breve modificherò i testcase, in particolare ne metterò uno in cui la risposta non sta nell’int
magari fate il 