Summary Files Commits Branches @commit @diff @stats
path: root / Year 2 / Design and analysis of algorithms / Practicum / Exam2 / 3-Game.cpp
diff options
context:
space:
mode:
Commite47c57a92d07f40d792b4a22c9934e0502c75aad (patch)
Author
 Syndamia <kamen@syndamia.com>
2023-05-21 20:14:51 +0300
Committer
 Syndamia <kamen@syndamia.com>
2023-05-21 20:14:51 +0300
Files468a0859ad209a3acc9f0f94edd468b00d375639 /Year 2/Design and analysis of algorithms/Practicum/Exam2/3-Game.cpp
uni-projects-e47c57a92d07f40d792b4a22c9934e0502c75aad.tar
uni-projects-e47c57a92d07f40d792b4a22c9934e0502c75aad.tar.gz
uni-projects-e47c57a92d07f40d792b4a22c9934e0502c75aad.zip
Parent6ffcfb17f058217f1353cbfd6fa3e8e9cc9681a4 (diff)
[DAAP] Added exercises from second exam
1 files changed, 55 insertions, 0 deletions
-rw-r--r--Year 2/Design and analysis of algorithms/Practicum/Exam2/3-Game.cpp55
diff --git a/Year 2/Design and analysis of algorithms/Practicum/Exam2/3-Game.cpp b/Year 2/Design and analysis of algorithms/Practicum/Exam2/3-Game.cpp
new file mode 100644
index 0000000..ea29789
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Practicum/Exam2/3-Game.cpp
@@ -0,0 +1,55 @@
+#include <iostream>
+#include <string>
+#include <queue>
+#include <vector>
+#include <algorithm>
+#include <utility>
+using namespace std;
+
+struct Edge {
+ long long end;
+ long long cmp;
+ long long points;
+};
+
+long long N, M, K;
+
+long long djikstra(long long s, vector<vector<Edge>>& graph) {
+ priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, less<pair<long long, long long>>> q;
+ vector<bool> visited(N);
+ vector<long long> dist(N);
+ dist[s] = 0;
+ q.push({ 0, s });
+ while (!q.empty()) {
+ auto c = q.top();
+ q.pop();
+
+ visited[c.second] = true;
+ for (Edge& e : graph[c.second]) {
+ if (visited[e.end]) continue;
+ long long nd = dist[c.second] + e.cmp;
+ if (dist[e.end] == 0 || nd > dist[e.end]) {
+ dist[e.end] = nd;
+ q.push({ nd, e.end });
+ }
+ }
+ }
+ return dist[N-1];
+}
+
+int main() {
+ ios::sync_with_stdio(false);
+ cin.tie(NULL);
+ cout.tie(NULL);
+
+ cin >> N >> M >> K;
+ vector<vector<Edge>> graph(N, vector<Edge>());
+ for (long long i = 0; i < M; i++) {
+ long long k1, k2, pi, ti;
+ cin >> k1 >> k2 >> pi >> ti;
+ k1--; k2--;
+ graph[k1].push_back({ k2, pi - ti, pi });
+ graph[k2].push_back({ k1, pi - ti, pi });
+ }
+ cout << K + djikstra(0, graph);
+}