diff options
Diffstat (limited to '03-algorithms_on_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 Binary files differnew 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 + |