POJ 2449

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <string>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
// #include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ull, ull> puu;

#define inf (0x3f3f3f3f)
#define lnf (0x3f3f3f3f3f3f3f3f)
#define eps (1e-9)
#define fi first
#define se second

bool sgn(double a, string select, double b) {
    if(select == "==")return fabs(a - b) < eps;
    if(select == "!=")return fabs(a - b) > eps;
    if(select == "<")return a - b < -eps;
    if(select == "<=")return a - b < eps;
    if(select == ">")return a - b > eps;
    if(select == ">=")return a - b > -eps;
}


//--------------------------

const ll mod = 1000000007;
const int maxn = 1010;

//use to bfs
struct Node {
    int v, c;
    Node(int _v = 0, int _c = 0) {
        v = _v, c = _c;
    }
    bool operator<(const Node &a)const {
        return c > a.c;
    }
};

//first is 'v' , second is 'cost'
vector<pii> edge[maxn];
vector<pii> zedge[maxn];
bool vis[maxn];
int dist[maxn];

void addedge(int u, int v, int w) {
    edge[v].push_back(make_pair(u, w));
    zedge[u].push_back(make_pair(v, w));
}

// id from 1
void dijkstra_heap(int n, int start) {
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++) dist[i] = inf;
    priority_queue<Node> que;
    while(!que.empty())que.pop();
    dist[start] = 0;
    que.push(Node(start, 0));
    Node tmp;
    while(!que.empty()) {
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if(vis[u])continue;
        vis[u] = true;
        for(int i = 0; i < edge[u].size(); i++) {
            int v = edge[u][i].fi;
            int cost = edge[u][i].se;
            if(!vis[v] && dist[v] > dist[u] + cost) {
                dist[v] = dist[u] + cost;
                que.push(Node(v, dist[v]));
            }
        }
    }
}

struct anode {
    int v;
    int f, g, h;
    anode(int _v = 0, int _f = 0, int _g = 0, int _h = 0) {
        v = _v, f = _f, g = _g, h = _h;
    }
    bool operator<(const anode &a)const {
        return f > a.f;
    }
};

int n, m;
int s, t, k;

bool Astar(int start) {
    if(s == t) {
        k++;
    }
    if(dist[start] == inf) {
        return false;
    }
    priority_queue<anode> que;
    while(!que.empty())que.pop();
    int num = 0;
    que.push(anode(start, dist[start], 0, dist[start]));
    while(!que.empty()) {
        anode tmp = que.top();
        que.pop();
        if(tmp.v == t) {
            num++;
            // printf("%d\n", tmp.g );
        }
        if(num >= k) {
            printf("%d\n", tmp.g );
            return true;
        }
        int u = tmp.v;
        for(int i = 0; i < zedge[u].size(); i++) {
            int v = zedge[u][i].fi;
            int cost = zedge[u][i].se;
            int g = tmp.g + cost;
            int h = dist[v];
            int f = g + h;
            que.push(anode(v, f, g, h));
        }
    }
    return false;
}


void solve() {
    while(~scanf("%d%d", &n, &m)) {
        for(int i = 1; i <= n; i++) {
            edge[i].clear();
            zedge[i].clear();
        }
        int u, v, w;
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
        }
        scanf("%d%d%d", &s, &t, &k);
        dijkstra_heap(n, t);
        if(!Astar(s)) {
            puts("-1");
        }
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    // iostream::sync_with_stdio(false);
    solve();
    return 0;
}