Catch The Bus

Computer Science Level 5

The National University of Singapore is built on a hill, so even if the distance from A to B seems short from the map, walking over the steep ladder is very exhausting. Fortunately, there's a shuttle bus service.

Suppose that NUS has $N$ buildings and $E$ bidirectional roads. A shuttle bus starts moving from building X to building Y (the detailed path will be given). At the same time, Chris starts walking from building A and wants to go to building B. Chris is as fast as the shuttle bus, but walking $k$ meters requires $k$ amount of energy (in Joules) while no energy is spent if he travels by a shuttle bus. What is the minimum amount of energy will Chris need to arrive at his destination?

Input File

Details and Assumptions

Chris walks as fast as the shuttle bus.
Chris can choose to wait at a building to hop onto a bus; no energy is spent in this process.
Chris can choose to drop by at any building the bus went through.
Chris can choose not to hop onto the bus.
The bus will not travel a building more than once.
Moving to any buildings is possible.

Input Format

The first line consists of two integers $N$ , $E$ - the number of buildings and the number of bidirectional roads.
The next $E$ lines each contains 3 integers $u, v, t$ describing a bidirectional road connecting building $u$ and $v$ of length $t$ .
The next line contains an integer $M$ , the number of buildings the shuttle bus go through.
The next line contains $M$ integers, describing the path of the shuttle bus in that order.
The last line contains two integers $A$ and $B$ , the starting building and the destination respectively.

$N$ and $E$ is as large as 82500 and 110000 respectively.
The length of the road does not exceed 100.
$M$ is as large as 1000.

Sample Input

Sample Output

Inspired by the number of ladders I need to climb to reach School of Computing, National University of Singapore.

The answer is 541667.

1 solution

João Areias
Jun 9, 2018

We can interpret this as a undirected wheighted graph in which the wheight of the nodes connected by the bus is 0, from there we can simply run dijkstra's shortest path algorithm and we get the result. Here is my c++11 implementation.

#include <bits/stdc++.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
using namespace std;

// Adjacency list of the graph map<source, map<destination, distance>>
typedef unordered_map<int, unordered_map<int, int> > Graph;
// Pairs are written in queue as pair<distance, destination> opposite of the graph
typedef priority_queue<pair<int, int>, vector<pair<int, int> >, greater< pair<int, int> > > PriorityQueue;

int dijkstra(const int start, const int goal,  Graph graph){
    PriorityQueue q;

    bool *visited = new bool[graph.size()];
    memset(visited, 0x00, graph.size()*sizeof(bool));
    visited[start] = true;

    int pos = start, distance = 0;
    q.push(make_pair(distance, pos));
    while(pos != goal){
        if(q.empty()){
            delete[](visited);
            return -1;
        }
        distance = q.top().first;
        pos = q.top().second;
        visited[pos] = true;
        q.pop();

        for(pair<int, int> p: graph[pos]){
            if(!visited[p.first]){
                q.push(make_pair(distance + p.second, p.first));
            }
        }
    }
    delete[](visited);
    return distance;
}


int main(){
    int N, E, M, A, B; // Name as shown in the problem
    Graph graph;

    // Getting input and building graph
    scanf("%d %d", &N, &E);
    for(int i=0; i<E; i++){
        int x, y, d;
        scanf("%d %d %d", &x, &y, &d);
        graph[x].find(y) == graph[x].end() ? graph[x][y] = d : graph[x][y] = min(graph[x][y], d);
        graph[y].find(x) == graph[y].end() ? graph[y][x] = d : graph[y][x] = min(graph[y][x], d);
    }

    scanf("%d", &M);
    int prev, next;
    scanf("%d", &prev);
    for(int i=1; i<M; i++){
        scanf("%d", &next);
        graph[prev][next] = 0;
        graph[next][prev] = 0;
        prev = next;
    }
    scanf("%d %d", &A, &B);
    printf("%d\n", dijkstra(A, B, graph));
}

Catch The Bus

Inspired by the number of ladders I need to climb to reach School of Computing, National University of Singapore.

The answer is 541667.

1 solution

0 pending reports