diff options
1 files changed, 53 insertions, 0 deletions
| -rw-r--r-- | Year 2/Design and analysis of algorithms/Practicum/Sofiaopen-spring-2023_lights.cpp | 53 |
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] << " "; + } +} |