[DAAP] Started work on exercise 151 from action arena

1 files changed, 44 insertions, 0 deletions

diff --git a/Year 2/Design and analysis of algorithms/Practicum/Action-151.cpp b/Year 2/Design and analysis of algorithms/Practicum/Action-151.cpp
new file mode 100644
index 0000000..d364251
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Practicum/Action-151.cpp
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <vector>
+#include <queue>
+using namespace std;
+
+struct Edge {
+	unsigned b;
+	unsigned p;
+	unsigned t;
+};
+
+int main() {
+	unsigned N, M, K;
+	cin >> N >> M >> K;
+	vector<vector<Edge>> graph(N, vector<Edge>());
+	for (unsigned i = 0; i < M; i++) {
+		unsigned ai, bi, pi, ti;
+		cin >> ai >> bi >> pi >> ti;
+		graph[ai-1].push_back({ bi-1, pi, ti });
+	}
+
+	// Dijkstra
+	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, less<pair<long long, long long>>> q;
+	vector<long> dist(N, -1);
+	dist[0] = 0;
+	vector<bool> visited(N, false);
+	q.push({ K, 0 });
+	while (!q.empty()) {
+		long long timeleft = q.top().first;
+		long long node = q.top().second;
+		q.pop();
+
+		visited[node] = true;
+		for (Edge& ne : graph[node]) {
+			if (visited[ne.b]) continue;
+			long long nd = (dist[node] > -1) * dist[node] + ne.p;
+			if (dist[ne.b] == -1 || nd < dist[ne.b]) {
+				dist[ne.b] = nd;
+				q.push({ timeleft - ne.t, ne.b });
+			}
+		}
+	}
+	cout << dist[N-1];
+}