summaryrefslogtreecommitdiff
path: root/cpp
diff options
context:
space:
mode:
authorSanto Cariotti <dcariotti24@gmail.com>2017-10-08 08:28:27 +0200
committerGitHub <noreply@github.com>2017-10-08 08:28:27 +0200
commitdd5332cbfe57f85ce48934cdac2c9f68c514b436 (patch)
treee7c6c6b957d9f1e167b318081f392aa86ab4ca58 /cpp
parenta38ce80c849be3d3e78d3349ef47c0b833cf937b (diff)
Create dijkstra.cc
Diffstat (limited to 'cpp')
-rw-r--r--cpp/dijkstra.cc74
1 files changed, 74 insertions, 0 deletions
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 <iostream>
+#include <utility>
+#include <list>
+#include <vector>
+#include <queue>
+#include <fstream>
+using namespace std;
+#define INF 999999
+
+typedef pair<int, int> pii;
+
+list<pii> adj[INF];
+int V;
+vector<int> previous(INF, -1);
+int dijkstra(int src, int dest) {
+ priority_queue<pii, vector<pii>, greater<pii> > pq;
+
+ vector<int> 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<int>& 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<int> path;
+ dijShortPath(dest, path);
+ for(auto const& i : path)
+ cout << i << ' ';
+
+ return 0;
+}