【POJ】2449 Remmarguts' Date（k短路）

http://poj.org/problem?id=2449

不会。。

百度学习。。

恩。

k短路不难理解的。

结合了a_star的思想。每动一次进行一次估价，然后找最小的（此时的最短路）然后累计到k

首先我们建反向边，跑一次从汇到源的最短路，将跑出来的最短路作为估价函数h

根据f=g+h

我们将源s先走，此时实际价值g为0，估价为最短路（他们的和就是s-t的最短路）

将所有s所连的边都做相同的处理，加入到堆中（假设此时到达的点为x，那么x的g等于s到这个点的边权，因为根据最优，g+h此时是从x到t的某个最优路线，将他们加入到堆）

当到达t的点数累计到了k，那么直接输出g值，如果s==t的话，k要先+1再进行astar（因为当s==t的时候，不经过一条边就满足了一个最短路，但这条路不能算，所以要剪掉，那么也就是k要加上1）

为什么呢。。。

因为我们每次操作就相当于拿出一条边，然后匹配它到t的最优路线形成一条s到t的路线。。。哎呀，自己慢慢理解。

// 2015.5.8 upd：听说关键字是g+f而不是f呢QAQ怪不得wc跪掉了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << #x << " = " << x << endl
#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int oo=1000000000, N=1005, M=100005;
int h[N], ihead1[N], ihead2[N], cnt1, cnt2, vis[N], n, m;
struct astr {
	int v, g, f;
	const bool operator< (const astr &b) const {
		return f+g>b.f+b.g;
	}
};
struct ED { int v, next, w; }e1[M], e2[M];
priority_queue<astr> pq;
queue<int> q;
inline void add(const int &u, const int &v, const int &w) {
	e1[++cnt1].next=ihead1[u]; ihead1[u]=cnt1; e1[cnt1].v=v; e1[cnt1].w=w;
	e2[++cnt2].next=ihead2[v]; ihead2[v]=cnt2; e2[cnt2].v=u; e2[cnt2].w=w;
}
void spfa(const int &s) {
	int u;
	for1(i, 1, n) h[i]=oo;
	CC(vis, 0);
	h[s]=0; vis[s]=1; q.push(s);
	while(!q.empty()) {
		u=q.front(); q.pop(); vis[u]=0;
		for(int i=ihead2[u]; i; i=e2[i].next) if(h[u]+e2[i].w<h[e2[i].v]) {
			h[e2[i].v]=h[u]+e2[i].w;
			if(!vis[e2[i].v]) { vis[e2[i].v]=1; q.push(e2[i].v); }
		}
	}
}
int getans(const int &s, const int &t, int k) {
	if(h[s]==oo) return -1;
	if(s==t) ++k;
	while(!pq.empty()) pq.pop();
	int num=0;
	astr now, tp; now.v=s; now.g=0; now.f=now.g+h[now.v];
	pq.push(now);
	while(!pq.empty()) {
		now=pq.top(); pq.pop();
		if(now.v==t) ++num;
		if(num==k) return now.g;
		for(int i=ihead1[now.v]; i; i=e1[i].next) {
			tp.v=e1[i].v; 
			tp.g=now.g+e1[i].w; 
			tp.f=tp.g+h[tp.v];
			pq.push(tp);
		}
	}
	return -1;
}

int main() {
	while(~scanf("%d%d", &n, &m)) {
		int u, v, w;
		cnt1=cnt2=0; CC(ihead1, 0); CC(ihead2, 0);
		rep(i, m) {
			read(u); read(v); read(w);
			add(u, v, w);
		}
		read(u); read(v); read(w);
		spfa(v);
		printf("%d
", getans(u, v, w));
	}
	return 0;
}

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

Sample Output

Source

POJ Monthly,Zeyuan Zhu