Destination Unknown

# The problem is from Benelux Algorithm Programming Contest 2013.

You are agent B100. A pair of prominently dressed circus artists is traveling over the roads of the city and your mission is to find out where they are headed. All we know is that they started at points and that they are heading for one of several possible destinations. They are in quite a hurry, though, so we are sure they will not take a detour to their destination.

Alas, prominently dressed as they may be, the duo is nowhere to be seen. Fortunately, you have an exceptional sense of smell. More specifically: your nose will never let you down. You can actually smell they have traveled along the road between intersections g and h.

Where is the elusive duo headed? Or are we still not sure?

A visual representation of the second sample. The duo is traveling from the gray circle to one of the two black circles, and you smelled them on the dashed line, so they could be heading to 6.

Input : 

On the first line one positive number: the number of test cases, at most 100. After that per test case:

• One line with three space-separated integers n, m, and t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000, and 1 ≤ t ≤ 100): the number of intersections in the city, the number of individual roads between those intersections, and the number of possible destinations respectively.
• One line with three space-separated integers s, g, and h (1 ≤ s, g, h ≤ n): the intersection the duo started from and the two intersections between which the duo has traveled, with g ≠ h.
• m lines with three space-separated integers a, b, and d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000), indicating that there is a bidirectional road between intersections a and b of length d.
• t lines with one integer x (1 ≤ x ≤ n): the possible destinations. All possible destinations are distinct and they are all different from s.
• There is at most one road between a pair of intersections. One of the m lines describes the road between g and h. This road is guaranteed to be on the shortest path to at least one of the possible destinations.

Output: 

Per test case - One line with one or more space-separated integers, indicating the destinations that the duo can still be headed for, in increasing order.

In order to solve this problem, you need to understand algorithms for finding the shortest path problems such as Dijkstra's algorithm.

You can get a basic idea about Dijkstra's algorithm from my previous post.  (https://advanceduno.blogspot.com/2022/08/dijkstras-algorithm.html)

Once you get all the input values (connections, weights, mid nodes, etc.), you need to execute Dijkstra's algorithm from the starting node where the duo left.

Next, you need to run Dijkstra's algorithm again from the first mid node and the second mid node.

Now, you calculated all the shortest paths from the starting node as well as from the first mid node and the second mid node.

All you need to do is compare whether passing through the mid nodes to the possible destinations is the same as the shortest path from the starting node to the destinations. 

The solution for the problem is down below:

#include<iostream>

#include<math.h>

#include<stdio.h>

#include<algorithm>

#include <queue>

#define MAX_SIZE 2000+1

#define endl "\n"

#define INF 987654321

using namespace std;

int iTestCases, iNodeNum, iConnectionNum, iDestNum, iStartPos, iMidFirst, iMidSecond;

int iResultSaveArray[MAX_SIZE];

int iNextNode;

int iNextWeight;

int Dijkstra(int iWantedNode, vector<pair<int, int>> iStoreConnectionArray[MAX_SIZE]) {

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > qSaveCount;

iResultSaveArray[iWantedNode] = 0;

qSaveCount.push({ 0, iWantedNode });

while (!qSaveCount.empty()) {

int iCurrentNode = qSaveCount.top().second;

int iCurrentWeight = qSaveCount.top().first;

qSaveCount.pop();

if (iResultSaveArray[iCurrentNode] < iCurrentWeight) {

continue;

}

for (int i = 0; i < iStoreConnectionArray[iCurrentNode].size(); i++) {

iNextNode = iStoreConnectionArray[iCurrentNode][i].first;

iNextWeight = iStoreConnectionArray[iCurrentNode][i].second;

if (iResultSaveArray[iNextNode] > iNextWeight + iCurrentWeight) {

iResultSaveArray[iNextNode] = iNextWeight + iCurrentWeight;

qSaveCount.push(make_pair(iResultSaveArray[iNextNode], iNextNode));

}

}

}

return 0;

}

void Reset() {

for (int j = 0; j <= iNodeNum; j++) {

iResultSaveArray[j] = INF;

}

}

int main(void)

{

ios::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

cin >> iTestCases;

for (int i = 0; i < iTestCases; i++) {

vector<pair<int, int>> iStoreConnectionArray[MAX_SIZE];

vector<int> iPredictDesVector;

vector<int> iPredictDesWeightVector;

cin >> iNodeNum >> iConnectionNum >> iDestNum;

cin >> iStartPos >> iMidFirst >> iMidSecond;

for (int j = 1; j <= iConnectionNum; j++) {

int tempA, tempB, tempWeight;

cin >> tempA >> tempB >> tempWeight;

iStoreConnectionArray[tempA].push_back(make_pair(tempB, tempWeight));

iStoreConnectionArray[tempB].push_back(make_pair(tempA, tempWeight));

}

for (int j = 0; j < iDestNum; j++) {

int iTempNum;

cin >> iTempNum;

iPredictDesVector.push_back(iTempNum);

}

Reset();

Dijkstra(iStartPos, iStoreConnectionArray);

int iToMidFirst = iResultSaveArray[iMidFirst];

int iToMidSecond = iResultSaveArray[iMidSecond];

for (int j = 0; j < iDestNum; j++) {

iPredictDesWeightVector.push_back(iResultSaveArray[iPredictDesVector[j]]);

}

int iTempVec[2001];

int iMidBetweenWeight;

Reset();

Dijkstra(iMidFirst, iStoreConnectionArray);

iMidBetweenWeight = iResultSaveArray[iMidSecond];

for (int j = 0; j < iDestNum; j++) {

if (iPredictDesWeightVector[j] < iResultSaveArray[iPredictDesVector[j]] + iMidBetweenWeight + iToMidSecond) {

iTempVec[j] = -1;

}

else {

iTempVec[j] = 1;

}

}

Reset();

Dijkstra(iMidSecond, iStoreConnectionArray);

for (int j = 0; j < iDestNum; j++) {

if (iPredictDesWeightVector[j] < iResultSaveArray[iPredictDesVector[j]] + iMidBetweenWeight + iToMidFirst && iTempVec[j] != 1) {

iTempVec[j] = -1;

}

else if (iPredictDesWeightVector[j] >= iResultSaveArray[iPredictDesVector[j]] + iMidBetweenWeight + iToMidFirst) {

iTempVec[j] = 1;

}

}

vector<int> ResultVec;

for (int j = 0; j < iDestNum; j++) {

if (iTempVec[j] == 1) {

ResultVec.push_back(iPredictDesVector[j]);

}

}

sort(ResultVec.begin(), ResultVec.end());

for (int j = 0; j < ResultVec.size(); j++) {

cout << ResultVec[j] << " ";

}

cout << "\n";

}

}

References:

https://www.acmicpc.net/problem/9370

https://cocoon1787.tistory.com/437