From 98e9ff8416cb99814f200866dc8eb44040b01e5b Mon Sep 17 00:00:00 2001 From: Syndamia Date: Mon, 22 May 2023 06:54:16 +0300 Subject: [DAAP/H2] Added initial solution to homework That times out --- .../Practicum/Homeworks/HW2-Zigzag.cpp | 47 ++++++++++++++++++++++ 1 file changed, 47 insertions(+) create mode 100644 Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp diff --git a/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp b/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp new file mode 100644 index 0000000..e5b9191 --- /dev/null +++ b/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp @@ -0,0 +1,47 @@ +#include +#include +#include +#include +using namespace std; + +long long N, M; +typedef pair Edge; + +void dfs(Edge& c, long long length, vector>& graph, bool lt, vector& visited, long long& shortest) { + if (c.second == N-1) { + shortest = min(shortest, length); + return; + } + + // cout << "From: " << c.second << " " << length << endl; + visited[c.second] = true; + for (Edge& e : graph[c.second]) { + if (visited[e.second]) continue; + if ((lt && c.second < e.second) || (!lt && c.second > e.second)) { + dfs(e, length + e.first, graph, !lt, visited, shortest); + } + } + visited[c.second] = false; +} + +int main() { + ios::sync_with_stdio(false); + cin.tie(NULL); + cout.tie(NULL); + + cin >> N >> M; + vector>> graph(N, vector>()); + for (long long i = 0; i < M; i++) { + long long ai, bi, di; + cin >> ai >> bi >> di; + ai--; bi--; + graph[ai].push_back({ di, bi }); + graph[bi].push_back({ di, ai }); + } + + long long shortest = 1000000005; + vector visited(N); + Edge s = {0, 0}; + dfs(s, 0, graph, true, visited, shortest); + cout << shortest << endl; +} -- cgit v1.3.1-26-gb76a