Algorithms : add 03-algorithms_on_graphs 04-paths_in_graphs

17 files changed, 189 insertions, 0 deletions

diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/00_paths_in_graphs.pdf b/03-algorithms_on_graphs/04-paths_in_graphs/00_paths_in_graphs.pdf
new file mode 100644
index 0000000..bf19599
--- /dev/null
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/00_paths_in_graphs.pdf
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 <iostream>
+#include <vector>
+#include <queue>
+
+using std::vector;
+using std::queue;
+using std::pair;
+using std::priority_queue;
+
+int distance(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) {
+  //write your code her
+  return -1;
+}
+
+int main() {
+  int n, m;
+  std::cin >> n >> m;
+  vector<vector<int> > adj(n, vector<int>());
+  vector<vector<int> > cost(n, vector<int>());
+  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
diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/negative_cycle.cpp b/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/negative_cycle.cpp
new file mode 100644
index 0000000..a48ee97
--- /dev/null
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/negative_cycle.cpp
@@ -0,0 +1,23 @@
+#include <iostream>
+#include <vector>
+
+using std::vector;
+
+int negative_cycle(vector<vector<int> > &adj, vector<vector<int> > &cost) {
+  //write your code here
+  return 0;
+}
+
+int main() {
+  int n, m;
+  std::cin >> n >> m;
+  vector<vector<int> > adj(n, vector<int>());
+  vector<vector<int> > cost(n, vector<int>());
+  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);
+  }
+  std::cout << negative_cycle(adj, cost);
+}
diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/tests/01 b/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/tests/01
new file mode 100644
index 0000000..f447c8b
--- /dev/null
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/tests/01
@@ -0,0 +1,5 @@
+4 4
+1 2 -5
+4 1 2
+2 3 2
+3 1 1
diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/tests/01.a b/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/tests/01.a
new file mode 100644
index 0000000..d00491f
--- /dev/null
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/tests/01.a
@@ -0,0 +1 @@
+1
diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/shortest_paths.cpp b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/shortest_paths.cpp
new file mode 100644
index 0000000..ac2007e
--- /dev/null
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/shortest_paths.cpp
@@ -0,0 +1,41 @@
+#include <iostream>
+#include <limits>
+#include <vector>
+#include <queue>
+
+using std::vector;
+using std::queue;
+using std::pair;
+using std::priority_queue;
+
+void shortest_paths(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, vector<long long> &distance, vector<int> &reachable, vector<int> &shortest) {
+  //write your code here
+}
+
+int main() {
+  int n, m, s;
+  std::cin >> n >> m;
+  vector<vector<int> > adj(n, vector<int>());
+  vector<vector<int> > cost(n, vector<int>());
+  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);
+  }
+  std::cin >> s;
+  s--;
+  vector<long long> distance(n, std::numeric_limits<long long>::max());
+  vector<int> reachable(n, 0);
+  vector<int> shortest(n, 1);
+  shortest_paths(adj, cost, s, distance, reachable, shortest);
+  for (int i = 0; i < n; i++) {
+    if (!reachable[i]) {
+      std::cout << "*\n";
+    } else if (!shortest[i]) {
+      std::cout << "-\n";
+    } else {
+      std::cout << distance[i] << "\n";
+    }
+  }
+}
diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/01 b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/01
new file mode 100644
index 0000000..a482de6
--- /dev/null
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/01
@@ -0,0 +1,9 @@
+6 7
+1 2 10
+2 3 5
+1 3 100
+3 5 7
+5 4 10
+4 3 -18
+6 1 -1
+1
diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/01.a b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/01.a
new file mode 100644
index 0000000..782d1c3
--- /dev/null
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/01.a
@@ -0,0 +1,6 @@
+0
+10
+-
+-
+-
+*
diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/02 b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/02
new file mode 100644
index 0000000..c90b966
--- /dev/null
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/02
@@ -0,0 +1,6 @@
+5 4
+1 2 1
+4 1 2
+2 3 2
+3 1 -5
+4
diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/02.a b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/02.a
new file mode 100644
index 0000000..a44b11a
--- /dev/null
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/tests/02.a
@@ -0,0 +1,5 @@
+-
+-
+-
+0
+*
diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/check b/03-algorithms_on_graphs/04-paths_in_graphs/check
new file mode 100755
index 0000000..b73ff99
--- /dev/null
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/check
@@ -0,0 +1,38 @@
+#! /bin/bash
+
+RESET="\033[0m"
+RED="\033[0;31m"
+GREEN="\033[0;32m"
+BROWN="\033[0;33m"
+
+BIN=/tmp/bin
+OUTA=/tmp/_outa
+OUTB=/tmp/_outb
+GPP_OPTS="-std=c++11 -O2"
+
+for path in $(find -name \*.cpp | sort); do
+    src=${path##*/}
+    dir=${path%/*}
+    echo -e "${RED}validate $BROWN$dir$RESET/$GREEN$src$RESET"
+    pushd $dir >/dev/null || exit 1
+    echo -e "   ${RED}compile $GREEN$src$RESET" && g++ $GPP_OPTS $src -o $BIN || exit 1
+    if [ -d tests ]; then
+        echo -e "   ${RED}check $GREEN$src$RESET"
+        for t in $(find ./tests -name "*[^a~]"|sort); do
+            if [ -f $t -a -f "$t.a" ]; then
+                cat $t | $BIN > $OUTA
+                cat $t.a > $OUTB
+                cmp $OUTA $OUTB >/dev/null
+                if [ $? -ne 0 ]; then
+                    echo -e "     $BROWN$t$RESET is ${RED}KO$RESET"
+                else
+                    echo -e "     $BROWN$t$RESET is ${GREEN}ok$RESET"
+                fi
+            fi
+        done
+    else
+        echo -e "   ${RED}no tests$RESET"
+    fi
+    popd > /dev/null
+done
+