[DAAP] Solved an exercise from olimpiici

1 files changed, 53 insertions, 0 deletions

diff --git a/Year 2/Design and analysis of algorithms/Practicum/Sofiaopen-spring-2023_lights.cpp b/Year 2/Design and analysis of algorithms/Practicum/Sofiaopen-spring-2023_lights.cpp
new file mode 100644
index 0000000..686319a
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Practicum/Sofiaopen-spring-2023_lights.cpp
@@ -0,0 +1,53 @@
+
+/* https://arena.olimpiici.com/#/catalog/756/problem/101958 */
+
+#include <iostream>
+#include <vector>
+#include <queue>
+#include <iostream>
+using namespace std;
+
+struct Path {
+	unsigned long long b;
+	unsigned long long s;
+	unsigned long long g;
+	unsigned long long r;
+};
+
+int main() {
+	unsigned long long N, M, S;
+	cin >> N >> M >> S;
+	vector<vector<Path>> crossroads(N+1);
+	for (long long i = 0; i < M; i++) {
+		unsigned long long ai, bi, si, gi, ri;
+		cin >> ai >> bi >> si >> gi >> ri;
+		crossroads[ai].push_back({ bi, si, gi, ri });
+		crossroads[bi].push_back({ ai, si, gi, ri });
+	}
+
+	// Dijkstra
+	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q;
+	vector<long> dist(N+1, -1);
+	vector<bool> visited(N+1, false);
+
+	q.push({ S, 1 });
+	while (!q.empty()) {
+		long long currTime = q.top().first;
+		long long currNode = q.top().second;
+		q.pop();
+
+		visited[currNode] = true;
+		for (Path& p : crossroads[currNode]) {
+			unsigned long long waitingTime = (currTime % (p.g + p.r) < p.g) ? 0 : p.g + p.r - (currTime % (p.g + p.r));
+			if (!visited[p.b] && (dist[p.b] < 0 || currTime + p.s + waitingTime < dist[p.b])) {
+				dist[p.b] = currTime + p.s + waitingTime;
+				q.push({ dist[p.b], p.b });
+			}
+		}
+	}
+
+
+	for (long long i = 2; i <= N; i++) {
+		cout << dist[i] << " ";
+	}
+}