Find almost-shortest path more efficiently

Question

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 answer[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(answer[i]);
        }
        camino.push_back(last_node);
        paths.push_back(camino);
        return;
    }
    for(int i = (int)p[t].size()-1; i >= 0; --i){
        answer[depth] = p[t][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.

Answer 1

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!