POJ 2449 第K短路

#include <iostream>
#include <string.h>
#include <queue>
#include <stdio.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n");
using namespace std;
typedef long long ll;
const ll inf = 0x7f7f7f7f;
const int maxn=1e5+10;
const int mod=1e9+7;
using namespace std;
ll num1=0,num2=0,n,m,s,t,r,k,h1[maxn],h2[maxn],d[maxn],flag[maxn];
struct node1
{
    ll x,y,z,next;
} mp1[maxn],mp2[maxn];
struct node
{
    ll v,c;
    node(ll vv,ll cc) : v(vv),c(cc) {}
    friend bool operator < (node x,node y)
    {
        return x.c+d[x.v]>y.c+d[y.v];
    }
};
void init()
{
    num1=0;
    num2=0;
    fillchar(h1,0);
    fillchar(h2,0);
}
inline void insert1(ll x,ll y,ll z)
{
    mp1[++num1].x=x;
    mp1[num1].y=y;
    mp1[num1].z=z;
    mp1[num1].next=h1[x];
    h1[x]=num1;
}
inline void insert2(ll x,ll y,ll z)
{
    mp2[++num2].x=x;
    mp2[num2].y=y;
    mp2[num2].z=z;
    mp2[num2].next=h2[x];
    h2[x]=num2;
}
void spfa()
{
    queue<ll>Q;
    Q.push(t);
    for(int i=1; i<=n; i++)
        d[i]=inf;
    d[t]=0;
    fillchar(flag,0);
    flag[t]=1;
    while(!Q.empty())
    {
        ll u=Q.front();
        Q.pop();
        flag[u]=0;
        for(int i=h1[u]; i; i=mp1[i].next)
        {
            ll v=mp1[i].y;
            if(d[v]>d[u]+mp1[i].z)
            {
                d[v]=d[u]+mp1[i].z;
                if(!flag[v])
                {
                    flag[v]=1;
                    Q.push(v);
                }
            }
        }
    }
}
ll astar()
{
    if(d[s]==inf)
        return -1;
    priority_queue<node>p;
    ll cnt=0;
    p.push(node(s,0));
    while(!p.empty())
    {
        node u=p.top();
        p.pop();
        if(u.v==t)
        {
            cnt++;
            if(cnt==k)
                return u.c;
        }
        for(int i=h2[u.v]; i; i=mp2[i].next)
        {
            ll y=mp2[i].y;
            p.push(node(y,u.c+mp2[i].z));
        }
    }
    return -1;
}
int main()
{
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        init();
        //read(s);read(t);read(k);read(r);
        while(m--)
        {
            ll x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            insert1(y,x,z);
            insert2(x,y,z);
        }
        scanf("%lld%lld%lld",&s,&t,&k);
        if(s==t)   //s到t认为不可达k++
            k++;
        spfa();
        ll _=astar();          //返回-1代表不能到达
        cout<<_<<endl;     //输出第k短路
    }
    return 0;
}