POJ 2449 Remmarguts' Date K短路

求圖中第k短路長度。

畢竟要求k短路，是以前k短路得暴出來。。

一個k短路顯然可以被分成一段非最短路和一段最短路。

（非最短路放在前面的目的是更加比對搜尋）

那麼最短路顯然就是非最短路長度為0的路。

而求出一個k短路顯然就是從最短路開始，不斷調整前面的非最短路，使其變成k短路，也就是說，調整的過程就是使前面的非最短路變長的過程，具體的方法顯然，對于非最短路和最短路的分界點，隻要調整其出邊，這條路就變長了。

是以可以考慮維護一個堆，其中存放着目前已經擴充出來的“非最短路”，以其“非最短路”長度+後半段最短路長度排序，優先挑總長度最短的路徑以上述方法調整。

對于這麼做的正确性，首先明确的是前k短路我們是需要全部搜出來的。然後如果我們不調整分界點的出邊而調整非最短路中的邊，顯然在之前的點必定擴充出了這種狀态。而通過堆維護走到目前狀态，意味着調整之前的邊不比目前狀态更優（因為之前調整了以後，即使走最短路到終點，長度也不會短于目前狀态沿最短路走向終點）。是以目前狀态肯定可以擴充出比之前那個狀态更短的路，是以優先擴充目前狀态。

于是bfs中遇到終點k次就是k短路啦。

至于輸出路徑的話，記錄一下目前狀态從哪個狀态擴充來的即可。

好像長度不能為0？是以如果起終點相同得排除掉長度0的路？

sizeof

并不能正确處理以指針傳入的數組，以前犯過這個毛病了，這次又犯。。該長記性了。。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = , M = ;
struct Data { int v, g, f; };
bool operator <(Data a, Data b) { return a.f > b.f; }
int d[N];
struct Graph {
    int h[N], p[M], v[M], w[M], cnt;
    void init() { cnt = ; memset(h, , sizeof h); }
    void add(int a, int b, int c) {
        p[++cnt] = h[a]; v[cnt] = b; w[cnt] = c; h[a] = cnt;
    }
    void spfa(int s) {
        static int q[M * ], vis[N];
        int f = , t = ;
        memset(d, , sizeof d);
        memset(vis, , sizeof vis);
        q[t++] = s; d[s] = ;
        while(f < t) {
            int u = q[f++];
            vis[u] = ;
            for (int i = h[u] ; i; i = p[i])
                if (d[v[i]] > d[u] + w[i]) {
                    d[v[i]] = d[u] + w[i];
                    if(!vis[v[i]]) vis[q[t++] = v[i]] = ;
                }
        }
    }
    int astar(int s, int t, int k) {
        priority_queue<Data> q;
        int cnt = ;
        if (d[s] == ) return -;
        q.push((Data) {s, , d[s]});
        while (!q.empty()) {
            Data u = q.top(); q.pop();
            if(u.v == t && ++cnt == k) return u.g;
            for(int i = h[u.v]; i; i = p[i])
                q.push((Data) {v[i], u.g + w[i], u.g + w[i] + d[v[i]]});
        }
        return -;
    }
} g, rg;
int main() {  
    int a, b, c, s, t, n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        g.init(); rg.init();
        while (m--) {
            scanf("%d%d%d", &a, &b, &c);
            g.add(a, b, c); rg.add(b, a, c);
        }
        scanf("%d%d%d", &s, &t, &k);
        rg.spfa(t);
        printf("%d\n", g.astar(s, t, k + (s == t)));
    }
    return ;
}
           

Remmarguts’ Date

Time Limit: 4000MS Memory Limit: 65536K

Total Submissions: 25334 Accepted: 6909

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