2015-S4 Convex Hull - Solution

# 2015-S4 Convex Hull - Solution

## Input

``````//Input

int hullThickness, numberOfIslands, numberOfSeaRoutes;
int startingIsland, endingIsland;

struct Edge
{
int destination, time, hullWear;
};

struct Node
{
vector<Edge> edges;
};

Node nodes[2001];

void addConnection(int a, int b, int t, int h)
{
Edge edge = Edge();
edge.destination = b;
edge.time = t;
edge.hullWear = h;
nodes[a].edges.push_back(edge);
}

{
cin >> hullThickness >> numberOfIslands >> numberOfSeaRoutes;
for (int i = 0; i < numberOfSeaRoutes; i++)
{
int a, b, t, h;
cin >> a >> b >> t >> h;
}
cin >> startingIsland >> endingIsland;
}
``````

## Solver Variables and Helper Functions

``````typedef pair<int, int> pii;

unsigned int distanceWithHullBurn[2001][201];
bool nodeInQueue[2001];

priority_queue<pii, vector<pii>, greater<pii> > nodeQueue;

void setDistance(int node, int hullBurn, unsigned int dist)
{
distanceWithHullBurn[node][hullBurn] = dist;
}

unsigned int getDistance(int node, int hullBurn)
{
return distanceWithHullBurn[node][hullBurn];
}

void setIsNodeInQueue(int node, bool inQueue)
{
nodeInQueue[node] = inQueue;
}

bool isNodeInQueue(int node)
{
return nodeInQueue[node];
}
``````

## Process Edge

``````void processEdge(int currentNode, Edge currentEdge)
{
for (int hullBurn = 0; hullBurn < hullThickness - currentEdge.hullWear; hullBurn++)
{
int alternateDistance = getDistance(currentNode, hullBurn) + currentEdge.time;

if (alternateDistance < getDistance(currentEdge.destination, currentEdge.hullWear + hullBurn))
{
setDistance(currentEdge.destination, currentEdge.hullWear + hullBurn, alternateDistance);

if (!isNodeInQueue(currentEdge.destination))
{
setIsNodeInQueue(currentEdge.destination, true);
nodeQueue.push(make_pair(alternateDistance, currentEdge.destination));
}
}
}
}
``````

## Solver

``````void solve()
{
memset(distanceWithHullBurn, 0x3F, sizeof(distanceWithHullBurn));
memset(nodeInQueue, false, sizeof(nodeInQueue));

nodeQueue.push(make_pair(0, startingIsland));

setDistance(startingIsland, 0, 0);
setIsNodeInQueue(startingIsland, true);

while (!nodeQueue.empty())
{
int currentNode = nodeQueue.top().second;
setIsNodeInQueue(currentNode, false);
nodeQueue.pop();

for (Edge currentEdge : nodes[currentNode].edges)
{
processEdge(currentNode, currentEdge);
}
}
}
``````

## Main Method

``````int main(int argc, char* argv[])
{
solve();

int fastestRoute = 0x3F3F3F3F;

for (int j = 0; j < hullThickness; j++)
{
fastestRoute = min(fastestRoute, (int)getDistance(endingIsland, j));
}

if (fastestRoute == 0x3F3F3F3F)
{
cout << -1 << endl;
}
else
{
cout << fastestRoute << endl;
}

return 0;
}
``````