SDA - hw11 - task1

#include <iostream>
#include <unordered_map>
#include <queue>
#include <set>
#include <climits>
using namespace std;

int periods[10000];
vector<int> distances(10000, INT_MAX);

unordered_map<int, unordered_map<int, int>> graph; //from, {to, cost}

int findShortest(int start, int end) {
    set<pair<int, int>> queue; //minDist, idx
    queue.insert({ 0, start });
    while (!queue.empty())
    {
        auto curr = *queue.begin();
        queue.erase(curr);

        if (curr.second == end)
        {
            return distances[curr.second];
        }

        auto neighbours = graph[curr.second];
        for (auto& neighbour : neighbours)
        {
            int waitingTime = (curr.first + neighbour.second) % periods[neighbour.first];
            int finalTime = curr.first + neighbour.second;
            if (waitingTime != 0 && neighbour.first != end)
            {
                finalTime += periods[neighbour.first] - waitingTime;
            }

            if (finalTime < distances[neighbour.first])
            {
                queue.erase({ distances[neighbour.first], neighbour.first });
                queue.insert({ finalTime, neighbour.first });
                distances[neighbour.first] = finalTime;
            }
        }
    }

    return -1;
}

int main()
{
    int v, e, start, end, a, b, c;
    cin >> v >> e >> start >> end;

    for (size_t i = 0; i < v; i++)
    {
        cin >> periods[i];
    }

    for (size_t i = 0; i < e; i++)
    {
        cin >> a >> b >> c;
        if (graph[a][b] == 0)
        {
            graph[a][b] = INT_MAX;
        }
        graph[a][b] = min(graph[a][b], c);
    }

    cout << findShortest(start, end);

}