diff options
[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.cpp | 55 |
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); +} |
