From 33d7d833615fee75b075e6bfb3a459cc02c4cc54 Mon Sep 17 00:00:00 2001 From: Jérémy Zurcher Date: Sun, 13 Nov 2016 23:14:10 +0100 Subject: Algorithms : add 03-algorithms_on_graphs 04-paths_in_graphs --- .../04-paths_in_graphs/01-dijkstra/dijkstra.cpp | 30 ++++++++++++++++++++++ .../04-paths_in_graphs/01-dijkstra/tests/01 | 6 +++++ .../04-paths_in_graphs/01-dijkstra/tests/01.a | 1 + .../04-paths_in_graphs/01-dijkstra/tests/02 | 11 ++++++++ .../04-paths_in_graphs/01-dijkstra/tests/02.a | 1 + .../04-paths_in_graphs/01-dijkstra/tests/03 | 5 ++++ .../04-paths_in_graphs/01-dijkstra/tests/03.a | 1 + 7 files changed, 55 insertions(+) create mode 100644 03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp create mode 100644 03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/01 create mode 100644 03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/01.a create mode 100644 03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/02 create mode 100644 03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/02.a create mode 100644 03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/03 create mode 100644 03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/03.a (limited to '03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra') diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp new file mode 100644 index 0000000..757a6c6 --- /dev/null +++ b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp @@ -0,0 +1,30 @@ +#include +#include +#include + +using std::vector; +using std::queue; +using std::pair; +using std::priority_queue; + +int distance(vector > &adj, vector > &cost, int s, int t) { + //write your code her + return -1; +} + +int main() { + int n, m; + std::cin >> n >> m; + vector > adj(n, vector()); + vector > cost(n, vector()); + for (int i = 0; i < m; i++) { + int x, y, w; + std::cin >> x >> y >> w; + adj[x - 1].push_back(y - 1); + cost[x - 1].push_back(w); + } + int s, t; + std::cin >> s >> t; + s--, t--; + std::cout << distance(adj, cost, s, t); +} diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/01 b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/01 new file mode 100644 index 0000000..88e4967 --- /dev/null +++ b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/01 @@ -0,0 +1,6 @@ +4 4 +1 2 1 +4 1 2 +2 3 2 +1 3 5 +1 3 diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/01.a b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/01.a new file mode 100644 index 0000000..00750ed --- /dev/null +++ b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/01.a @@ -0,0 +1 @@ +3 diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/02 b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/02 new file mode 100644 index 0000000..99e01ee --- /dev/null +++ b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/02 @@ -0,0 +1,11 @@ +5 9 +1 2 4 +1 3 2 +2 3 2 +3 2 1 +2 4 2 +3 5 4 +5 4 1 +2 5 3 +3 4 4 +1 5 diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/02.a b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/02.a new file mode 100644 index 0000000..1e8b314 --- /dev/null +++ b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/02.a @@ -0,0 +1 @@ +6 diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/03 b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/03 new file mode 100644 index 0000000..0af6eeb --- /dev/null +++ b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/03 @@ -0,0 +1,5 @@ +3 3 +1 2 7 +1 3 5 +2 3 2 +3 2 diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/03.a b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/03.a new file mode 100644 index 0000000..3a2e3f4 --- /dev/null +++ b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/tests/03.a @@ -0,0 +1 @@ +-1 -- cgit v1.2.3