ACM ICPC - 4210 - Almost Shortest Path

# Problem Info

Type: Regional
Continent: South America
Year: 2008
Link: 4210 - Almost Shortest Path

# Problem Statement

Finding the shortest path that goes from a starting point to a destination point given a set of points and route lengths connecting them is an already well known problem, and it's even part of our daily lives, as shortest path programs are widely available nowadays.
Your program must answer not the shortest path, but the almost shortest path. The almost shortest path is defined as the shortest path that goes from a starting point to a destination point such that no route between two consecutive points belongs to any shortest path from the starting point to the destination. There could exist no possible answer as well.

# Explanation

There's a presentation I've written to teach how to solve the problem. It is in Spanish, I don't have enough time now to write the explanation here but I will as soon as I can.

The presentation: 4210-AlmostShortestPath.pdf

# Code

The C++ that solves the problem is the following(4210.cpp):

```#include <stdint.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

#define INF 99999999

using namespace std;

uint32_t arcs[500 * 500];
uint32_t rarcs[500 * 500];

struct my_pair {

uint16_t u;
uint16_t p;

bool operator<(const my_pair& other) const{
return this->p >= other.p;
}
};

vector<uint32_t> dijkstra(uint16_t init, uint16_t size, uint32_t* matrix) {
priority_queue<my_pair> queue;
vector<uint32_t> result(size, INF);
bool used[size];
my_pair working, working2;
uint32_t i, dist;

for (i = 0; i < size; ++i)
used[i] = false;

result[init] = 0;

working.u = init;
working.p = 0;
queue.push(working);
while (!queue.empty()) {
working = queue.top();
queue.pop();

if (used[working.u])
continue;
used[working.u] = true;

for (i = 0; i < size; i++) {
dist = matrix[working.u * size + i];
if (result[working.u] + dist < result[i]) {
result[i] = result[working.u] + dist;
working2.u = i;
working2.p = result[i];
queue.push(working2);
}
}
}
return result;

}

int main() {

uint16_t n, m;
uint16_t i, j;
uint16_t s, d;
uint16_t u, v, p;
vector<uint32_t> res_d1, res_d2, res_d3;

cin >> n >> m;
while (n != 0) {

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
arcs[i * n + j] = INF;
rarcs[i * n + j] = INF;
}
}

cin >> s >> d;

for (i = 0; i < m; ++i) {
cin >> u >> v >> p;
arcs[u * n + v] = p;
rarcs[v * n + u] = p;
}

res_d1 = dijkstra(s, n, arcs);
res_d2 = dijkstra(d, n, rarcs);

uint32_t min_path = res_d1[d];
/* Delete arcs that are part of a shortest path */
for (u = 0; u < n; ++u) {
for (v = 0; v < n; ++v) {
uint16_t dist = arcs[u * n + v];
if (res_d1[u] + dist + res_d2[v] == min_path) {
arcs[u * n + v] = INF;
}
}
}

res_d3 = dijkstra(s, n, arcs);
if (res_d3[d] == INF)
cout << -1 << '\n';
else
cout << res_d3[d] << '\n';
cin >> n >> m;
}

return 0;
}
```