# Find almost-shortest path more efficiently

I'm trying to solve a SPOJ problem, which is code SAMER08A at this link.

The problem is that when I ran my code in my IDE with all the examples given in the problem, the code works perfectly. But when running it in SPOJ, it exceeds the time limit of 2 seconds.

I am frustrated because I have worked so hard on it. I would love some advice and help.

#include <vector>
#include <iostream>
#include <queue>
using namespace std;

typedef pair <int, int> dist_node;
typedef pair <int, int> edge;
const int MAXN = 500;
const int INF = 1 << 30;
vector <edge> g[MAXN];
int d[MAXN];
vector<int> p[MAXN];
int last_node;
vector<vector<int> > paths;

int dijkstra(int s, int n,int t){
for (int i = 0; i <= n; ++i){
d[i] = INF;  p[s].push_back(-1);
}
priority_queue < dist_node, vector <dist_node>,greater<dist_node> > q;
d[s] = 0;
q.push(dist_node(0, s));
while (!q.empty()){
int dist = q.top().first;
int cur = q.top().second;
q.pop();
if (dist > d[cur]) continue;
for (int i = 0; i < g[cur].size(); ++i){
int next = g[cur][i].first;
int w_extra = g[cur][i].second;
if (d[cur] + w_extra < d[next]){
d[next] = d[cur] + w_extra;
p[next].clear();
p[next].push_back(cur);
q.push(dist_node(d[next], next));
}
else if(d[cur] + w_extra == d[next]){
p[next].push_back(cur);
}
}
}
return d[t];
}

void findpath (int t, int depth){
if(t == 0){
vector<int> camino;
for(int i = depth-1; i >= 0; --i){
}
camino.push_back(last_node);
paths.push_back(camino);
return;
}
for(int i = (int)p[t].size()-1; i >= 0; --i){
findpath(p[t][i], depth+1);
}
}

void findAlmostShortestPath(){

for(int k = 0; k<paths.size();k++){
vector<int> camino = paths[k];
for(int i = 0;i<camino.size()-1;i++){
int x = camino[i];
int y = camino[i+1];
for(int j = 0; j < g[x].size() ; j++){
if(g[x][j].first == y){
g[x][j].second =INF;
break;
}
}
break;
}
}
}

int main(){
int n,m;
int w,s;
bool seguir = true;
while(seguir){
cin>>n>>m;
cin>>w>>s;
last_node=s;

if(n == 0 & m == 0){
break;
}
for (int i = 0; i < m; ++i){
int u, v, w;
cin >> u >> v >> w;
g[u].push_back(edge(v, w));
}
int i;
i = dijkstra(w, n,s);
findpath(s, 0);
findAlmostShortestPath();
i = dijkstra(w, n, s);

if(i==INF){
i =-1;
}
cout<<i<<endl;

for(int i = 0; i < g[i].size(); i++){
g[i].clear();
}
}

return 0;
}


I would be so grateful if you could help me since I've worked on this for hours, and it's my first SPOJ problem that I have tried to solve.

Here's a partial/basic structured implementation of the problem. It works for the first two cases, but the last case comes back twice as large. I saw this question on SO and thought your version was highly over complicated and probably inefficient due to data structure choices. There isn't any reason to provide and pass around multi-dimensional vectors and such, and there's no doubt you could drop that priority_queue.

Take a look at mine and see if you could simplify yours. Since your logic, I'm assuming, works you should be able to catch the last case without too much effort. I wasn't intending to finish it I just wanted to see if it could easily be done without such complexity. It isn't meant to replace yours, it's just to provide a second opinion on it.

Take a look:

Note: Some of the variable are there because of the problem distription. Some validations are missing because the test data didn't require them.

#include <iostream>
#include <vector>
#include <algorithm>

using std::cin;
using std::cout;
using std::vector;
using std::sort;

const int START = 0;
const int END   = 1;
const int DIST  = 2;

vector<int> getPaths(int **, int, int, int);
int getDistance(int **, int , int , int , int , int&);

int main (void)
{

int input = 0;
int n = 0, m = 0, s = 0, d = 0, u = 0, v = 0, p = 0;
int shortestPath = 0;
int nextShortestPath = 0;
int **pathPtr;
vector<int> allDistances;

cin >> n;
if (n >= 2 && n <= 500) {
cin >> m;
if (m >= 1 && m <= 100000) {
cin >> s;
cin >> d;
pathPtr = new int*[m];
for (int i = 0; i < m; ++i) {
pathPtr[i] = new int[3];
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> input;
pathPtr[i][j] = input;
}
}
allDistances = getPaths(pathPtr, m, s, d);
sort(allDistances.begin(), allDistances.end());
for (unsigned int i = 0; i < allDistances.size(); ++i) {
if (allDistances[i] != 0) {
shortestPath = allDistances[i];
if (i + 1 < allDistances.size()) {
nextShortestPath = allDistances[i + 1];
break;
} else {
nextShortestPath = -1;
break;
}
}
}
cout << nextShortestPath;
}
}
cin.get();
return 0;
}

vector<int> getPaths(int **paths, const int m, const int s, const int d) {
vector<int> distances;
int distance = 0;
int shortest = 0;
int tempShort = 0;
for (int i = 0; i < m; ++i) {
if (paths[i][START] == s) {
distance = 0;
if (paths[i][END] == d) {
distances.push_back(paths[i][DIST]);
} else {
distances.push_back(getDistance(paths, i, i + 1, m, d, distance));
}
}
}
return distances;
}

int getDistance(int **paths, int i, int j, int m, int d, int &distance) {
if (paths[j][START] == paths[i][END]) {
distance += paths[i][DIST];
if (paths[j][END] != d) {
if (j < m) {
distance += getDistance(paths, j, j + 1, m, d, distance);
} else {
distance = 0;
}
} else {
distance += paths[j][DIST];
}
} else {
getDistance(paths, i, j + 1, m, d, distance);
}
return distance;
}


Let me know if it improved your running time any. Good Luck!

• Man, I have tried to fix the code so I can run it in Spoj but it is not wokring for me, can you give me any advice on how to improve my code without actually changing everything? Thanks a lot! :) – Nicolas May 20 '13 at 23:04
• Unfortunately if you're not meeting the time constraints you almost have no choice. I think you should ask yourself, "what is this priority_queue for?" It needs to be removed! There isn't any reason to even care about any priority. The data sets are given starting at 0 and continuing. All paths must start at 0, so those and their paths are the only ones you're interested in. That was more of the point of my example which, by the way, took no time to do. Maybe you should look and see how I'm able to find the shortest path by only following paths that begin with 0. – ChiefTwoPencils May 22 '13 at 23:37
• I just ran that code with the 3 test cases that they give in the problem, and it doesn't work with the last case :( – Nicolas May 23 '13 at 4:52
• That's what I said. Read the post again. I just wrote what I was thinking would be an easy way to meet the requirements. You'll have to resolve that. – ChiefTwoPencils May 23 '13 at 5:31
• Oh i'm sorry! Gonna try that man :) Thanks a lot! – Nicolas May 23 '13 at 14:29