Problem A
Not the Best
Input: standard input
Output: standard output
Time Limit: 1 second

Abul isnot the best student in his class; neither is he the best player in his team.Not that he is bad; he is really good, but unfortunately not the best.

Last semesterour “not quite the best” Abul took a course on algorithms. In one of theassignments he was required to find the shortest path from a given vertex xto another vertex y in a weighted directed graph. As you have probablyalready guessed, he rarely managed to find the shortest path; instead he alwaysended up finding the k^th (2 k 10)shortest path from x to y. If he was fortunate enough and theshortest k paths from x to y had the same length, he wasgiven credit for his solution.

For example, forthe graph above, Abul was asked to find the shortest path from vertex 5to vertex 2. The shortest 7 paths from vertex 5 to vertex 2are listed below in non-decreasing order of length. For this graph Abulwas able to find the 5^th shortest path which could be either 54 3 2 5 1 2 or 5 1 2 5 4 3 2, each with length 15.

Given adescription of the graph, source vertex x, target vertex y,and the value of k, you need to find out the length of the path Abulcomputed. You may assume that there exists at least one path from xto y in the given graph.

Input

The input maycontain multiple test cases.

The first lineof each test case contains two integers n (2 n 100)and m (1 m 1000) giving respectively thenumber of vertices, and the number of edges in the graph. Each vertex in thegraph is identified by a unique integer in [1, n]. The second line ofthe test case contains the values of , y and k(1 x, y 100, x y, 2 k 10). Each of the next m lines contains three integers u,v and l (1 u,v 100, 0 l 10000) specifying adirected edge of length l from vertex u to vertex v.

The inputterminates with two zeros for n and m.

Output

For each test case in the inputoutput a line containing an integer giving the length of the k^thshortest path in the graph. If the graph does not have at least k pathsfrom x to y, output a 1 instead.

SampleInput                              Output for Sample Input

0 0

Problemsetter: Rezaul Alam Cowdhury, University of Texas at Austin

Specialthanks: Md. Kamruzzaman, EPS

zerojudge/post/1322319700

#include <stdio.h>
#include <queue>
#include <vector>
#define oo 0xffffff
using namespace std;
struct arc {
    int to, w;
    arc(int x, int y) : to(x), w(y) {}
};
vector<arc> g[105], invg[105];
int toEDdis[105], fromSTdis[105], used[105], kpath[105];
void prepare(int st, int ed, int k, int n) { // spfa
    int i, tn;
    for(i = 1; i <= n; i++)
        toEDdis[i] = oo, used[i] = 0;
    queue<int> Q;
    toEDdis[ed] = 0;
    Q.push(ed);
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        used[tn] = 0;
        for(i = 0; i < invg[tn].size(); i++) {
            if(toEDdis[invg[tn][i].to] > toEDdis[tn] + invg[tn][i].w) {
                toEDdis[invg[tn][i].to] = toEDdis[tn] + invg[tn][i].w;
                if(!used[invg[tn][i].to]) {
                    used[invg[tn][i].to] = 1;
                    Q.push(invg[tn][i].to);
                }
            }
        }
    }
}
struct cmp {
    bool operator()(arc a, arc b) {
        return a.w > b.w;
    }
};
void sol_kpath(int st, int ed, int k, int n) {
    prepare(st, ed, k, n);
    priority_queue<arc, vector<arc>, cmp> pQ;
    int i;
    arc tn(0,0);
    for(i = 1; i <= n; i++)
        fromSTdis[i] = oo, kpath[i] = 0;
    pQ.push(arc(st, toEDdis[st]));
    while(!pQ.empty()) {
        tn = pQ.top();
        pQ.pop();
        if(kpath[tn.to] >= k)
            continue;
        tn.w -= toEDdis[tn.to];
        kpath[tn.to]++, fromSTdis[tn.to] = tn.w;
        if(kpath[ed] == k) {
            printf("%d\n", fromSTdis[ed]);
            return;
        }
        for(i = 0; i < g[tn.to].size(); i++) {
            pQ.push(arc(g[tn.to][i].to, tn.w+g[tn.to][i].w+toEDdis[g[tn.to][i].to]));
        }
    }
    puts("-1");
}
int main() {
    int n, m, x, y, w, i, st, ed, k;
    while(scanf("%d %d", &n, &m) == 2) {
        if(!n && !m)    break;
        for(i = 1; i <= n; i++)
            g[i].clear(), invg[i].clear();
        scanf("%d %d %d", &st, &ed, &k);
        arc e(0,0);
        while(m--) {
            scanf("%d %d %d", &x, &y, &w);
            e.to = y, e.w = w;
            g[x].push_back(e);
            e.to = x;
            invg[y].push_back(e);
        }
        sol_kpath(st, ed, k, n);
    }
    return 0;
}