SDA - hw11 - task3

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <queue>
#include <climits>


using namespace std;
int n, m, k; //crossroads, tunnels
int finalIdx;

struct Tunnel {
    int from;
    int to;
    int kg;
    int time;
    Tunnel(int from, int to, int kg, int time)
        : from(from), to(to), kg(kg), time(time) {}
};

unordered_map<int, vector<Tunnel>> graph;
//from to kg time

bool isPossible(int kg) {
    priority_queue<pair<int, int>> queue; //time, idx
    unordered_map<int, int> times; //idx, time
    times[0] = 0;
    queue.push({ 0, 0 });
    vector<bool> visited(n, false);

    while (!queue.empty())
    {
        auto curr = queue.top();
        int timeSoFar = curr.first;
        int currIdx = curr.second;
        visited[currIdx] = true;

        auto neighbours = graph[currIdx];
        for (auto neighbour : neighbours)
        {
            int time = timeSoFar + neighbour.time;
            if (neighbour.kg > kg || time > k || visited[neighbour.to])
            {
                continue;
            }

            if (neighbour.to == finalIdx)
            {
                return true;
            }

            if (times.count(neighbour.to) == 0 || times[neighbour.to] > time)
            {
                queue.push({ time, neighbour.to });
                times[neighbour.to] = time;
            }
        }

        while (!queue.empty() && visited[queue.top().second])
        {
            queue.pop();
        }
    }
    return false;
}

int binarySearch(int min, int max) {
    int result = -1;
    while (min <= max)
    {
        int mid = min + (max - min) / 2;

        if (isPossible(mid)) {
            result = mid;
            max = mid - 1;
        }
        else {
            min = mid + 1;
        }
    }
    return result;
}

int main() {
    cin >> n >> m >> k;
    int maxKg = 0;
    finalIdx = n - 1;
    int u, v, c, t;

    for (size_t i = 0; i < m; i++)
    {
        cin >> u >> v >> c >> t;
        graph[u - 1].push_back({ u - 1, v - 1, c, t });
        if (c > maxKg)
        {
            maxKg = c;
        }
    }

    cout << binarySearch(0, maxKg);
}