Finding kth shortest path (uva-10740, dijkstra).cpp

/* Finding k-th shortest path */
/* Author : M. A. Rafsan Mazumder */

#include <bits/stdc++.h>

using namespace std;

#define MAX 105
typedef pair<int, int> PII;
int x, y, k;
vector<pair<int, int> > adj[MAX];
vector<int> dist[MAX];

void dijkstra(int s)
{
    priority_queue<PII, vector<PII>, greater<PII> > pq;
    pq.push(make_pair(0, s));
    while(!pq.empty()){
        int u = pq.top().second;
        int u_cost = pq.top().first;
        pq.pop();
        if(dist[u].size() == k) continue;
        // In some cases there will be multiple edges between same nodes
        // For those cases
        /*else {
            int len = dist[u].size();
            if(len != 0){
                if(dist[u][len-1] == u_cost) continue;
            }
        }*/
        dist[u].push_back(u_cost);
        for(int i=0; i<adj[u].size(); i++){
            int v = adj[u][i].first;
            int u_to_v = adj[u][i].second;
            if(dist[v].size() == k) continue;
            pq.push(make_pair(u_cost + u_to_v, v));
        }
    }
}

int main()
{
    //freopen("in.txt", "r", stdin);
    int n, m;
    while(scanf("%d %d", &n, &m)){
        if(n == 0 && m == 0) break;
        for(int i=0; i<MAX; i++){
            adj[i].clear();
            dist[i].clear();
        }
        scanf("%d %d %d", &x, &y, &k);
        for(int i=0; i<m; i++){
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
            adj[u].push_back(make_pair(v, c));
        }
        dijkstra(x);
        int res;
        if(dist[y].size() < k) res = -1;
        else res = dist[y][k-1];
        printf("%d\n", res);
    }
}