可重復(fù)邊k短路，現(xiàn)在一想其實(shí)很簡單，就一個(gè)估界函數(shù)的設(shè)計(jì)。反向建圖，用從終點(diǎn)到其余各點(diǎn)的最短距離做估界函數(shù)就好了。
#include <iostream>
#include <queue>
#include <stdio.h>
using namespace std;
#define N 1005
#define M 200005
#define INF 1 << 29
struct edge
{
int ed, cost;
int next;
}e[M];
struct node
{
int id, w, f;
};
priority_queue<node> q;
bool operator < (const node a, const node b)
{
return a.f > b.f;
}
int sp, head1[N], head2[N], d[N], rank[N];
bool mark[N];
void init(int n)
{
sp = 0;
for(int i = 0; i <= n; i++)
{
head1[i] = head2[i] = -1;
rank[i] = 0;
}
}
void add(int a, int b, int c)
{
e[sp].ed = b, e[sp].cost = c;
e[sp].next = head1[a];
head1[a] = sp++;
e[sp].ed = a, e[sp].cost = c;
e[sp].next = head2[b];
head2[b] = sp++;
}
void dijkstra(int st, int n)
{
while(!q.empty()) q.pop();
node u, v;
for(int i = 0; i <= n; i++)
{
d[i] = INF;
mark[i] = 0;
}
u.id = st, u.f = 0;
d[st] = 0;
q.push(u);
while(!q.empty())
{
u = q.top(), q.pop();
if(mark[u.id]) continue;
mark[u.id] = 1;
for(int i = head2[u.id]; i != -1; i = e[i].next)
if(!mark[e[i].ed] && d[u.id] + e[i].cost < d[e[i].ed])
{
d[e[i].ed] = d[u.id] + e[i].cost;
v.id = e[i].ed, v.f = d[e[i].ed];
q.push(v);
}
}
}
int astar(int st, int ed, int n, int k)
{
dijkstra(ed, n);
if(d[st] == INF) return -1;
// printf("%d\n", d[st]);
// system("pause");
while(!q.empty()) q.pop();
node u, v;
u.id = st, u.w = 0, u.f = d[st];
q.push(u);
while(!q.empty())
{
u = q.top(), q.pop();
rank[u.id]++;
if(rank[ed] == k) return u.w;
if(rank[u.id] > k) continue;
for(int i = head1[u.id]; i != -1; i = e[i].next)
{
v.id = e[i].ed, v.w = u.w + e[i].cost;
v.f = v.w + d[e[i].ed];
q.push(v);
}
}
return -1;
}
int main()
{
// freopen("in", "r", stdin);
int n, m, a, b, c, st, ed, k, ans;
while(scanf("%d %d", &n, &m), n + m)
{
init(n);
scanf("%d %d %d", &st, &ed, &k);
for(int i = 0; i < m; i++)
{
scanf("%d %d %d", &a, &b, &c);
add(a, b, c);
}
if(st == ed) k++;
ans = astar(st, ed, n, k);
printf("%d\n", ans);
}
return 0;
}