POJ 2449 Remmarguts' Date【SPFA】【A*】

Remmarguts' Date
Time Limit: 4000MS
Memory Limit: 65536K
Total Submissions: 21978
Accepted: 5982
Description
"Good man never makes girls wait or breaks an appointment!"said the mandarin duck father. Softly touching his little ducks' head, he told them a story.  "Prince Remmarguts lives in his kingdom UDF – United Delta of Freedom. One day their neighboring country sent them Princess Uyuw on a diplomatic mission."  "Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)"  Being interested in the trade development and such a lovely girl, Prince Remmarguts really became enamored. He needs you - the prime minister's help!  DETAILS: UDF's capital consists of N stations. The hall is numbered S, while the station numbered T denotes prince' current place. M muddy directed sideways connect some of the stations. Remmarguts' path to welcome the princess might include the same station twice or more than twice, even it is the station with number S or T. Different paths with same length will be considered disparate. 
Input
The first line contains two integer numbers N and M (1 <= N <= 1000, 0 <= M <= 100000). Stations are numbered from 1 to N. Each of the following M lines contains three integer numbers A, B and T (1 <= A, B <= N, 1 <= T <= 100). It shows that there is a directed sideway from A-th station to B-th station with time T.  The last line consists of three integer numbers S, T and K (1 <= S, T <= N, 1 <= K <= 1000).
Output
A single line consisting of a single integer number: the length (time required) to welcome Princess Uyuw using the K-th shortest path. If K-th shortest path does not exist, you should output "-1"(without quotes) instead.
Sample Input
2 2 1 2 5 2 1 4 1 2 2
Sample Output
14
Source
POJ Monthly,Zeyuan Zhu
제목 대의: 공주는 왕자에게 k의 짧은 경로를 통해 그녀를 찾아가라고 했다.는 N개의 점, M개의 단방향 모서리 그림을 보여 줍니다.줬어요.
시작점 s(왕자가 있는 점), 끝점 t(공주가 있는 점)와 k.물음: K 단락은 얼마입니까?
사고방식: 처음으로 K단락의 문제를 풀었다.A*+SPFA로 했어요.다음은 이 알고리즘을 간단히 말씀드리겠습니다.
체인식 전방향 별 저장도를 사용합니다.다음 절차를 밟아서 하다.
(1) 벡터가 있는 모든 모서리를 두 개의 다른 모서리 세트(Edges, Edges1)에 양방향 및 대칭 이동으로 저장합니다.모서리 세트를 대칭 이동하여
원하는 종점 t를 원점으로 하고 SPFA 또는 Dijkstra를 이용하여 모든 점에서 t까지의 가장 짧은 경로를 구하며 Dist[i] 배열로 점 i를 표시한다
점 t까지의 최단 거리.
(2) 소스 s를 대기열에 추가하는 우선 대기열을 만듭니다.
(3) 우선 대기열에서 가장 작은 점 p를 꺼내고 점 p==t가 있으면 t의 출대 횟수를 계산한다.만약 현재 경로 길이가 s라면
t의 k 단락 길이까지 알고리즘이 끝납니다.그렇지 않으면 p와 연결된 모든 변을 옮겨다니며 확장된 p의 인접점 정보를 추가합니다
우선 순위 대기열에서 찾습니다.
주의: s==t일 때 k+1 단락을 계산해야 합니다.s에서 t까지의 거리가 0인 길은 이 k단거리 안에 속하지 않기 때문에
s==t일 때 k=k+1을 다시 k단락을 구하면 된다.이것도 이 문제의 관건 중의 하나다.

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 1100;
const int MAXM = 110000;
const int INF = 0xffffff0;

struct EdgeNode
{
    int to;
    int w;
    int next;
}Edges[MAXM],Edges1[MAXM];

int Head[MAXN],Head1[MAXN];

struct Node
{
    int to;
    int g,f;
    bool operator < (const Node &r) const
    {
        if(r.f == f)
            return r.g < g;
        return r.f < f;
    }
};
int vis[MAXN],Dist[MAXN];

int A_Star(int start,int end,int N,int k)
{
    Node e,ne;
    int Cnt = 0;
    priority_queue<Node> que;
    if(start == end)
        k++;
    if(Dist[start] == INF)
        return -1;
    e.to = start;
    e.g = 0;
    e.f = e.g + Dist[e.to];
    que.push(e);
    while( !que.empty() )
    {
        e = que.top();
        que.pop();
        if(e.to == end)
            Cnt++;
        if(Cnt == k)
            return e.g;

        for(int i = Head[e.to]; i != -1; i = Edges[i].next)
        {
            ne.to = Edges[i].to;
            ne.g = e.g + Edges[i].w;
            ne.f = ne.g + Dist[ne.to];
            que.push(ne);
        }
    }
    return -1;
}
void SPFA(int s,int N)
{
    for(int i = 0; i <= N; ++i)
        Dist[i] = INF;
    memset(vis,0,sizeof(vis));
    vis[s] = 1;
    Dist[s] = 0;
    queue<int> Q;
    Q.push(s);
    while( !Q.empty() )
    {
        int u = Q.front();
        Q.pop();
        vis[u] = 0;
        for(int i = Head1[u]; i != -1; i = Edges1[i].next)
        {
            int temp = Dist[u] + Edges1[i].w;
            if(temp < Dist[Edges1[i].to])
            {
                Dist[Edges1[i].to] = temp;
                if(!vis[Edges1[i].to])
                {
                    vis[Edges1[i].to] = 1;
                    Q.push(Edges1[i].to);
                }
            }
        }
    }
}

int main()
{
    int N,M,u,v,w,s,t,k;
    while(~scanf("%d%d",&N,&M))
    {
        memset(Edges,0,sizeof(Edges));
        memset(Edges1,0,sizeof(Edges1));
        memset(Head,-1,sizeof(Head));
        memset(Head1,-1,sizeof(Head1));
        for(int i = 0; i < M; ++i)
        {
            scanf("%d%d%d",&u,&v,&w);
            Edges[i].to = v;
            Edges[i].w = w;
            Edges[i].next = Head[u];
            Head[u] = i;

            Edges1[i].to = u;
            Edges1[i].w = w;
            Edges1[i].next = Head1[v];
            Head1[v] = i;
        }
        scanf("%d%d%d",&s,&t,&k);
        SPFA(t,N);
        int kthlenth = A_Star(s,t,N,k);
        printf("%d
",kthlenth);
    }

    return 0;
}