From dd5332cbfe57f85ce48934cdac2c9f68c514b436 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sun, 8 Oct 2017 08:28:27 +0200 Subject: Create dijkstra.cc --- cpp/dijkstra.cc | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 74 insertions(+) create mode 100644 cpp/dijkstra.cc diff --git a/cpp/dijkstra.cc b/cpp/dijkstra.cc new file mode 100644 index 0000000..8fed8c0 --- /dev/null +++ b/cpp/dijkstra.cc @@ -0,0 +1,74 @@ +#include +#include +#include +#include +#include +#include +using namespace std; +#define INF 999999 + +typedef pair pii; + +list adj[INF]; +int V; +vector previous(INF, -1); +int dijkstra(int src, int dest) { + priority_queue, greater > pq; + + vector dist(INF, INF); + previous.resize(V); + pq.push(make_pair(0, src)); + dist[src] = 0; + while(!pq.empty()) { + int u = pq.top().second; + pq.pop(); + + for(auto const& i : adj[u]) { + int v = i.first; + int w = i.second; + + if(dist[v] > dist[u] + w) { + dist[v] = dist[u] + w; + pq.push({dist[v], v}); + previous[v] = u; + } + } + } + + return dist[dest]; +} + +void dijShortPath(int v, list& path) { +/* example: +v = 6; +v = previous[6] (5) +v = previous[5] (2) +... +*/ + for(; v != -1; v = previous[v]) + path.push_front(v); +} + +int main() { +/* +numVertici numArchi +sorgente destinazione +vertice1 vertice2 peso +... +*/ + cin >> V; + int e, sorg, dest; + cin >> e >> sorg >> dest; + int u, v, w; + for(int i = 0; i < e; i++) { + cin >> u >> v >> w; + adj[u].push_back(make_pair(v, w)); + } + cout << dijkstra(sorg, dest) << endl; + list path; + dijShortPath(dest, path); + for(auto const& i : path) + cout << i << ' '; + + return 0; +} -- cgit v1.2.3-18-g5258