SPOJ 3405. Almost Shortest Path solution

This can be solved with 2 Dijkstra's . Use the first one to find all shortest paths , delete those edges and then do another Dijkstra's for answer . This has a time limit of 0.199 seconds so it has to be optimized a lot . My solution passed in 0.01 seconds .


#include<bits/stdc++.h>
using namespace std;
inline int scan(){
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9'){
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
#define pb push_back
#define mp make_pair
class compare{
    public :
    bool operator()(pair<int,int> a,pair<int ,int > b){
        return a.second>b.second;
    }
};
int main(){
    while(1){
        int n=scan(),m=scan();
        if(n==0&&m==0){
            break;
        }
        int s=scan(),d=scan();
        vector<pair<int,int> > v[501];
        priority_queue<pair<int,int>,vector<pair<int,int> >,compare> q;
        while(m--){
            int x=scan(),y=scan(),w=scan();
            v[x].pb(mp(y,w));
        }
        int dist[501];
        memset(dist,-1,sizeof(dist));
        vector<int> prev[501];
        dist[s]=0;
        q.push(mp(s,0));
        while(!q.empty()){
            int node= q.top().first;
            q.pop();
            int x=v[node].size();
            for(int i=0;i<x;i++){
                int next=v[node][i].first;
                int weight=v[node][i].second;
                if(dist[node]+weight<dist[next]||dist[next]==-1){
                    dist[next]=dist[node]+weight;
                    q.push(mp(next,dist[next]));
                    prev[next].clear();
                    prev[next].pb(node);
                }
                else if(weight + dist[node]==dist[next]){
                    prev[next].pb(node);
                }
            }
        }
        if(dist[d]==-1){
            printf("-1\n");
            continue;
        }
        bool mark[501][501]={0};
        queue<int> qu;
        bool visited[501]={0};
        qu.push(d);
        visited[d]=1;
        while(!qu.empty()){
            int node=qu.front();
            qu.pop();
            int x=prev[node].size();
            for(int i=0;i<x;i++){
                mark[prev[node][i]][node]=1;
                if(!visited[prev[node][i]]){
                qu.push(prev[node][i]);
                visited[prev[node][i]]=1;
                }
            }
        }
        int dista[501];
        memset(dista,-1,sizeof(dista));
        dista[s]=0;
        q.push(mp(s,0));
        while(!q.empty()){
            int node= q.top().first;
            q.pop();
            int x=v[node].size();
            for(int i=0;i<x;i++){
                int next =v[node][i].first;
                if(mark[node][next]!=1){
                    int weight= v[node][i].second;
                    if(dista[node]+weight<dista[next]||dista[next]==-1){
                        dista[next]=dista[node]+weight;
                        q.push(mp(next,dista[next]));
                    }
                }
            }
        }
        printf("%d\n",dista[d]);
    }
}