撰写“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.
输入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).输出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.样例输入
2 2 1 2 5 2 1 4 1 2 2
样例输出
14
题意：RT；
题解：
这道题我之前碰到过，跑了裸的第k短路dijkstra，然后GG，复杂度为 O(K*(N+M)*log(N+M))。
- 我们知道，使用优先队列bfs时，第k次找到终点所经过的距离就是第k最短路。
- 我们设置f(x)为节点x到终点的距离。
- 这样我们得到这样一个简单的A*算法：
- 反向dijkstra得到每个点到终点的距离。
- 建立一个二叉堆，储存二元组(x,dist+f(x)),x为节点编号，dist为st到x走过的距离，起初堆中只有(s,0+f(x))。
- 从二叉堆中取出dist+f(x),然后沿着x出发的每条边y进行拓展。如果vis(y)<=k，就把新的二元组（y,Dist-f(x)+w(x,y)+f(y)）重新加入堆中。（Dist=dist+f(x)方便结构体定义）
- 重复2、3，知道第k次取出包含终点ed的二元组，此时的dist就是第k短路。
- 虽然不够快，但是能A。
//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan_d(T &ret) {
char c;
int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='?'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='?')?-1:1;
ret=(c=='?')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
inline void outt(int x) {
if(x>9) outt(x/10);
putchar(x%10+'0');
}
const int MAXN=1010;
const int maxn=1e5+10;
struct edge {
int v;
int w;
edge(int _v=0,int _w=0):v(_v),w(_w) {}
} e[2*maxn],E[2*maxn];
int tot=0,Tot=0;
int head[MAXN],Head[MAXN];
int nxt[2*maxn],Nxt[2*maxn];
void addedge(int u,int v,int w) {
e[++tot].v=v;
e[tot].w=w;
nxt[tot]=head[u];
head[u]=tot;
E[++Tot].v=u;
E[Tot].w=w;
Nxt[Tot]=Head[v];
Head[v]=Tot;
}
int f[MAXN];
int vis[MAXN];
int n,m,u,v,w,st,ed,k;
struct node{
int x;
int dist;
node(int _x,int _dist):x(_x),dist(_dist){}
bool operator < (const node &a)const{
return dist>a.dist;
}
};
priority_queue<node>que;
void dijkstra() {
rep(i,1,n)f[i]=INF,vis[i]=0;
while(!que.empty())que.pop();
f[ed]=0;
que.push(node(ed,0));
node tmp(0,0);
while(!que.empty()){
tmp=que.top();
que.pop();
int u=tmp.x;
if(vis[u])continue;
vis[u]=1;
for(int i=Head[u];i;i=Nxt[i]){
int v=E[i].v,w=E[i].w;
if(!vis[v]&&f[v]>f[u]+w){
f[v]=f[u]+w;
que.push(node(v,f[v]));
}
}
}
}
int A_() {
rep(i,1,n)vis[i]=0;
while(!que.empty())que.pop();
que.push(node(st,0+f[st]));
node tmp(0,0);
while(!que.empty()){
tmp=que.top();que.pop();
int u=tmp.x,dist=tmp.dist;
++vis[u];
if(vis[u]>k)continue;
if(u==ed&&vis[u]==k)return dist;
for(int i=head[u];i;i=nxt[i]){
int v=e[i].v,w=e[i].w;
que.push(node(v,dist-f[u]+w+f[v]));
}
}
return -1;
}
void input() {
rep(i,1,m) {
scan_d(u);
scan_d(v);
scan_d(w);
addedge(u,v,w);
}
scan_d(st);
scan_d(ed);
scan_d(k);
if(st==ed)k++;
}
int main() {
scan_d(n);
scan_d(m);
input();
dijkstra();
cout<<A_();
return 0;
}