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; }
