OnTheRoad.cpp

#include <bits/stdc++.h>
#define MAX 300
#define INF (numeric_limits<int>::max()/2)

using namespace std;

typedef int weight;
typedef int id;

vector<int> dijkstra(int start, vector< vector < pair <weight, id> > >& graph) {

	vector < int >  dist(MAX, INF); 
	vector < bool >  seen(MAX, 0); 
	priority_queue< pair< weight, id >, vector< pair <int, int> >, greater<pair <int, int> > > q;
	/**
	for (int i=0; i<graph.size(); ++i) {
		dist[i][i] = 0;
	}
	**/
	q.emplace(0, start);
	dist[start] = 0;
	
	while (!q.empty()) {
		
		auto top = q.top(); q.pop();
		if (!seen[top.second]) {
			seen[top.second] = true;
			for (auto neighbour : graph[top.second]) {
				weight cDist = dist[neighbour.second];
				weight thisDist = top.first + neighbour.first;
				if (thisDist < cDist) {
					dist[neighbour.second] = thisDist;
					q.emplace(thisDist, neighbour.second);
				}
			}
		}
		
	}
	return dist;
}

int main() {
	
	int nNodes, nEdges, nTowns; id start, end;
	cin >> nNodes >> nEdges >> nTowns >> start >> end;
	
	vector< vector < pair <weight, id> > > graph(nNodes);

	id x, y; weight w;
	for (int i=0; i<nEdges; i++) {
		cin >> x >> y >> w;
		graph[x].emplace_back(w,y);
		graph[y].emplace_back(w,x);
	}
	
	vector<weight> shortestPathsFromSrc = dijkstra(start, graph);
	vector<weight> shortestPathsToEnd = dijkstra(end, graph);
	
	weight shortestDistanceSoFar = INF; id bestTown = INF;
	
	for (int i=0; i<nTowns; i++) {
		id intermediaryTown;
		cin >> intermediaryTown;

		weight temp = shortestPathsFromSrc[intermediaryTown] + shortestPathsToEnd[intermediaryTown];
		if (temp < shortestDistanceSoFar) {
			bestTown = intermediaryTown;
			shortestDistanceSoFar = temp;
		} else if (temp == shortestDistanceSoFar) {
			bestTown = (intermediaryTown < bestTown ? intermediaryTown : bestTown);
		}
	}
	
	cout << shortestDistanceSoFar << " " << bestTown;
	
}

Test cases

 	Time 	Memory 	Result 	Score
Test Set #1 	  	+0.00
Case #1.1 	0.006 seconds 	256.0 kB 	Correct! 	
Test Set #2 	  	+0.00
Case #2. 1 	1.679 seconds 	27.88 MB 	Fatal Signal 	
Case #2. 2 	1.745 seconds 	27.88 MB 	Fatal Signal 	
Case #2. 3 	1.792 seconds 	27.80 MB 	Fatal Signal 	
Case #2. 4 	0.061 seconds 	2.875 MB 	Fatal Signal 	
Case #2. 5 	0.003 seconds 	256.0 kB 	Correct! 	
Case #2. 6 	0.094 seconds 	2.875 MB 	Fatal Signal 	
Case #2. 7 	2.147 seconds 	27.89 MB 	Fatal Signal 	
Case #2. 8 	0.003 seconds 	256.0 kB 	Correct! 	
Case #2. 9 	1.578 seconds 	27.88 MB 	Fatal Signal 	
Case #2.10 	0.004 seconds 	256.0 kB 	Correct! 	
Case #2.11 	1.518 seconds 	21.88 MB 	Fatal Signal 	
Test Set #3 	  	+0.00
Case #3.1 	0.003 seconds 	256.0 kB 	Correct! 	
Case #3.2 	0.097 seconds 	2.875 MB 	Fatal Signal 	
Case #3.3 	2.147 seconds 	27.89 MB 	Fatal Signal 	
Case #3.4 	0.061 seconds 	2.875 MB 	Fatal Signal 	
Case #3.5 	1.909 seconds 	27.88 MB 	Fatal Signal 	
Case #3.6 	1.039 seconds 	22.00 MB 	Fatal Signal 	
Test Set #4 	  	+0.00
Case #4. 1 	1.745 seconds 	27.88 MB 	Fatal Signal 	
Case #4. 2 	1.507 seconds 	27.82 MB 	Fatal Signal 	
Case #4. 3 	0.006 seconds 	256.0 kB 	Correct! 	
Case #4. 4 	1.518 seconds 	21.88 MB 	Fatal Signal 	
Case #4. 5 	0.003 seconds 	256.0 kB 	Correct! 	
Case #4. 6 	1.578 seconds 	27.88 MB 	Fatal Signal 	
Case #4. 7 	1.039 seconds 	22.00 MB 	Fatal Signal 	
Case #4. 8 	0.061 seconds 	2.875 MB 	Fatal Signal 	
Case #4. 9 	0.004 seconds 	256.0 kB 	Correct! 	
Case #4.10 	0.097 seconds 	2.875 MB 	Fatal Signal 	
Case #4.11 	2.147 seconds 	27.89 MB 	Fatal Signal 	
Case #4.12 	1.661 seconds 	27.85 MB 	Fatal Signal 	
Case #4.13 	1.679 seconds 	27.88 MB 	Fatal Signal 	
Case #4.14 	0.003 seconds 	256.0 kB 	Correct! 	
Case #4.15 	1.719 seconds 	22.14 MB 	Fatal Signal 	
Case #4.16 	1.747 seconds 	27.88 MB 	Fatal Signal 	
Case #4.17 	1.792 seconds 	27.80 MB 	Fatal Signal 	
Case #4.18 	0.094 seconds 	2.875 MB 	Fatal Signal 	
Case #4.19 	1.191 seconds 	21.75 MB 	Wrong Answer 	
Case #4.20 	0.113 seconds 	2.875 MB 	Fatal Signal 	
Case #4.21 	1.909 seconds 	27.88 MB 	Fatal Signal 	
Case #4.22 	1.506 seconds 	22.12 MB 	Fatal Signal 	
	Total Score: 	0