Rezumat problemă

graph

#146

Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu N noduri şi M arce, fiecare arc având o distanţă de valoare întreagă. Dându-se N, M şi cele M arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri.

Grigore Moisil 2013

Fișiere Candale Silviu (silviu) Cosmin Tutunaru concurs

Clasa 11 Teoria Grafurilor Grafuri cu costuri Sortare topologică Algoritmul lui Dijkstra

Rezolvă

Detalii

Problema	graph	Operații I/O	graph.in/graph.out
Limita timp	1 secunde	Limita memorie	Total: 64 MB / Stivă 8 MB
Id soluție	#58088490	Utilizator	ilie demian (insertokname)
Fișier	graph.cpp	Dimensiune	1.83 KB
Data încărcării	13 Mai 2025, 15:03	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

graph.cpp:1:1: error: expected unqualified-id before string constant
 "// one of the official contest solutions\n#include <cstdio>\n#include <vector>\n\n#define infile \"graph.in\"\n#define outfile \"graph.out\"\n\n#define nMax 1513\n#define inf (1<<29)\n\nusing namespace std;\n\nvector <pair<int, int> > v[nMax];\nint dp[nMax];\n\nint sorted[nMax];\nint h[nMax];\n\nint ap[nMax];\nint n, m;\n\nstatic void read()\n{\n    int i, x, y, z;\n\n    scanf(\"%d %d\\n\", &n, &m);\n\n    for(i = 0; i < m; i++) {\n        scanf(\"%d %d %d\", &x, &y, &z);\n\n        v[x].push_back(make_pair(y, z));\n        ap[y]++;\n    }\n}\n\nstatic int getNode()\n{\n    int i;\n\n    for(i = 1; i <= n; i++)\n        if (ap[i] == 0)\n            return i;\n\n    return -1;\n}\n\nstatic void addNode(int x)\n{\n    ap[x] = -1;\n\n    for(unsigned i = 0; i < v[x].size(); i++)\n        ap[v[x][i].first]--;\n}\n\nstatic void sort()\n{\n    int i, node;\n\n    for(i = 0; i < n; i++) {\n        node = getNode();\n        addNode(node);\n\n        sorted[i] = node;\n        h[node] = i;\n    }\n}\n\nstatic void solve()\n{\n    int i, j, node;\n\n    for(i = 0; i < n; i++) {\n        for(j = 0; j < n + 1; j++)\n            dp[j] = inf;\n\n        dp[i + 1] = 0;\n\n        for(j = h[i + 1]; j < n; j++) {\n           node = sorted[j];\n\n           if(dp[node] == inf)\n               continue;\n\n           for (unsigned k = 0; k < v[node].size(); k++)\n               dp[v[node][k].first] = min(dp[v[node][k].first], dp[node] + v[node][k].second);\n        }\n\n        for(j = 1; j < n + 1; j++)\n            if(dp[j] == inf)\n                printf(\"x \");\n            else\n                printf(\"%d \", dp[j]);\n\n        printf(\"\\n\");\n    }\n}\n\nint main()\n{\n    freopen(infile, \"r\", stdin);\n    freopen(outfile, \"w\", stdout);\n\n    read();\n    sort();\n    solve();\n\n    fclose(stdin);\n    fclose(stdout);\n\n    return 0;\n}\n"
 ^

Cum funcționează evaluarea?