传送门:

http://www.qscoj.cn/#/problem/show/1987

童心未泯的帆宝和乐爷 Edit

Time Limit: 10000 MS     Memory Limit: 256 MB
Submit Status

6·1即将来临,游乐园推出了新的主题活动,雨过天晴,帆宝乐爷童心未泯,准备一探究竟。

兴奋的他们一入园便和孩子们打成一片,不知不觉便走散了。

当他们意识到的时候,只能通过手机来确认对方的位置。

他们当然想尽快找到对方,然而由于孩子们实在是太多,只能选择距离稍远的但是游客稀少的路会合。

帆宝希望找到第kk 短的路径,这条路径是他认为的幸运路径。

帆宝迫切地想知道该条路径的长度,而乐于助人的你也一定会帮助她的。

Input

第一行三个整数n,m,kn,m,k ,分别表示游乐园的景点数目、景点之间的道路数目以及路径长度从小到大排列时希望选择的序号。

第二行两个整数S,TS,T ,分别表示帆宝乐爷所在景点的编号。

接下来mm 行,每行三个整数u,v,wu,v,w ,表示编号为uu 和vv 的景点之间有一条长度为ww 的单向通路。

1≤n≤1000,0≤m≤100000,1≤k≤1000,1≤S,T,u,v≤N,1≤w≤1001≤n≤1000,0≤m≤100000,1≤k≤1000,1≤S,T,u,v≤N,1≤w≤100

Output

第一行一个整数xx ,表示所选路径的长度

无解输出−1−1

Sample input and output

3 3 2
1 2
1 2 2
1 3 4
3 2 1
5

Hint

Source

2018 UESTC ACM Training for Search Algorithm and String
 
分析:
第k短路,A*+spfa解决
属于模板题
但是我A*+优化的迪杰斯特拉超时 。。。
mmp
还拿着在poj交了一道题,可以过啊
应该是测试数据不适合迪杰斯特拉吧
。。。。。。。。。。(自我安慰)
 
code:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int AX = 1e5+;
const int MAXN = 1e3+;
int n,m,k;
int s,t;
int tot;
int retot;
struct edge
{
int to,w;
int next1;
} G[AX],RG[AX]; struct Node
{
int v;
int f,h,g;
bool operator < (const Node &a) const
{
return f==a.f? g>a.g : f>a.f;
}
}; int dis[MAXN];
int head[MAXN];
int rehead[AX];
int vis[MAXN]; void add_edge(int u,int v,int c)
{
G[tot].to=v;
G[tot].w=c;
G[tot].next1=head[u];
head[u]=tot++; RG[retot].to=u;
RG[retot].w=c;
RG[retot].next1=rehead[v];
rehead[v]=retot++;
}
void SPFA()
{
for(int i=; i<=n; i++) dis[i]=INF;
dis[t]=;
queue<int> Q;
Q.push(t);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
for(int i=rehead[u]; i!=-; i=RG[i].next1)
{
int v=RG[i].to ;
int w=RG[i].w ;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
Q.push(v);
}
}
}
} int Astar(Node a)//A*算法
{
memset(vis,,sizeof(vis));
if(dis[s]==INF) return -;//如果没有与S相连的点
if(s==t) k++;
priority_queue<Node> Q;
Q.push(a);
while(!Q.empty())
{
Node tmp=Q.top();
Q.pop();
int v=tmp.v;
vis[v]++;
if(vis[t]==k) return tmp.g;
for(int i=head[v]; i!=-; i=G[i].next1)
{
Node p;
p.v=G[i].to;
p.h=dis[G[i].to];
p.g=tmp.g+G[i].w;
p.f=p.g+p.h;
Q.push(p);
}
}
return -;
} int main()
{
tot=;
retot=;
memset(head,-,sizeof head);
memset(rehead,-,sizeof rehead);
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d",&s,&t);
int x,y,w;
for(int i=; i<m; i++)
{
scanf("%d%d%d",&x,&y,&w);
add_edge(x,y,w);
}
SPFA();
Node a;
a.v=s;
a.g=;
a.h=dis[s];
a.f=a.g+a.h;
int g=Astar(a);
printf("%d\n",g);
return ;
}

也贴一下超时的A*+优化的迪杰斯特拉

#include <iostream>
#include <cstdio>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<memory>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
#define max_v 10010
#define INF 99999999
struct node
{
int to,val;
node(){}
node(int a,int b)
{
to=a;
val=b;
}
};
vector<node> e[max_v],ee[max_v];
int n,m,k;
int vis[max_v];
int dis[max_v];
void addEdge(int x,int y,int val)
{
e[x].push_back(node(y,val));
ee[y].push_back(node(x,val));//把图反向
}
void Dijkstra(int s,int t)
{
priority_queue<int,vector<int>,greater<int> > q;
while(!q.empty())
q.pop(); for(int i=;i<=n;i++)
vis[i]=,dis[i]=INF; vis[t]=,dis[t]=,q.push(t); int u,len;
while(!q.empty())
{
u=q.top();
q.pop(); len=ee[u].size();
for(int i=;i<len;i++)
{
node v=ee[u][i];
if(dis[v.to]>dis[u]+v.val)
{
dis[v.to]=dis[u]+v.val;
if(!vis[v.to])
{
q.push(v.to);
vis[v.to]=;
}
}
}
vis[u]=;
}
}
struct Anode
{
int h,g,id;
Anode(int a,int b,int c){h=a;g=b;id=c;}
bool operator<(Anode a) const
{
return h+g>a.h+a.g;
}
};
priority_queue<Anode> Q; int Astar(int s,int t)//A*算法
{
while(!Q.empty())
Q.pop();
Q.push(Anode(,dis[s],s)); int len,num;
num=;
while(!Q.empty())
{
Anode u=Q.top();
Q.pop(); if(u.id==t)
++num;
if(num>=k)
return u.h; len=e[u.id].size();
for(int i=;i<len;i++)
{
node v=e[u.id][i];
Q.push(Anode(u.h+v.val,dis[v.to],v.to));
}
}
return -;//不能连通或者没有k短路
}
int main()
{
int x,y,v,s,t;
while(~scanf("%d %d %d",&n,&m,&k))
{
scanf("%d %d",&s,&t);
for(int i=;i<max_v;i++) e[i].clear(),ee[i].clear();
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&v);
addEdge(x,y,v);
}
if(s==t) k++;
Dijkstra(s,t);
printf("%d\n",Astar(s,t));
}
return ;
}
//有向图 第k短路模板
04-14 11:10
查看更多