CCC 2015 S4 : Convex Hull

/*
Thanks to kobortor (Joey) for help!

CCC 2015 S4 : Convex Hull

Basically, the way to approach this problem is sort of a 3 Queue Dijkstra's (forgive me if I spelled the name wrong).
What I did, is, create 2 classes that would respresent an Island, and a canal link between two islands. And from there,
I would try to calculate the largest distance from A to B, with the hull height being above 0, duh.

Dealing with input is really straight forward, since it's a bi-directional graph, we want to make sure that our graph
is traversable both ways, this is an important step.

For the algorithm, as said above, we're dealing with 3 queues (each stores the best possible distance, hull height, and the
island that we're currently checking).

You want to get the maximum possible hull height OR the max possible distance, with respect to the hull being
above 0 in height, then just push the maximum values to the queue.

Before printing the distance, check if we've reached the destination, if we haven't, print -1. We know that we haven't reached
the destination when the shortest path to it is INFINITY (as labeled from the start)

And that's about it.
*/

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int MAXN = 10010;
typedef long long ll;

int convexHull, N, M, start, finish;

struct canal;

//all hail joey

struct island{
    vector<canal> outgoing;
    int shortestpath, hull;
    island() {
        shortestpath = INT_MAX; //who cares?
        hull = -1;
    }
};

struct canal{
    island* destination;
    ll weight;
    ll hulldamage;

    canal(island* dest, ll w, ll dmg){
        destination = dest;
        weight = w;
        hulldamage = dmg;
    }
};

island islands[MAXN]; //safety
int a, b, c, d;

int totalWeight, damage;

void Dijkstra(){
    queue<island*> toCheck;
    queue<int> distance;
    queue<int> maxHull;

    islands[a].shortestpath = 0;

    distance.push(0);
    toCheck.push(&islands[start]);
    maxHull.push(convexHull);

    while(!toCheck.empty()){

        island* front = toCheck.front();
        int dist = distance.front();
        int height = maxHull.front();

        toCheck.pop();
        maxHull.pop();
        distance.pop();

        for(canal &c : front->outgoing){
            int str = height - c.hulldamage;
            int time = dist + c.weight;
            island* destination = c.destination;
            if((time < destination->shortestpath || str > destination->hull) && str > 0){
                destination->shortestpath = std::min(time, destination->shortestpath);
                destination->hull = std::max(destination->hull, str);
                toCheck.push(destination);
                maxHull.push(str);
                distance.push(time);
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &convexHull, &N, &M);
    while(M--){
        scanf("%d%d%d%d", &a, &b, &c, &d);
        islands[a].outgoing.emplace_back(canal(&islands[b], c, d));
        islands[b].outgoing.emplace_back(canal(&islands[a], c, d));
    }
    scanf("%d%d", &start, &finish);
    Dijkstra();
    if(islands[finish].shortestpath == INT_MAX){ //broken..
        printf("-1");
    } else {
        printf("%d", islands[finish].shortestpath);
    }
}