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