题意:

k短路

题解:

A*

当然是抄了zzd的代码

然而需要特判

为什么把bool改成int爆空间!!!

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=+,M=N*N,Inf=<<;
struct Gragh
{
int cnt,x[M],y[M],z[M],nxt[M],fst[N];
void set()
{
cnt=;
memset(fst,,sizeof fst);
}
void add(int a,int b,int c)
{
x[++cnt]=a,y[cnt]=b,z[cnt]=c;
nxt[cnt]=fst[a],fst[a]=cnt;
}
}A,B;
struct Path
{
int g,f,to;
vector <int> path;
bool vis[N];
bool operator < (const Path x) const
{
if (f==x.f)return g>x.g;
return f>x.f;
}
};
bool cmp(Path a,Path b)
{
if (a.f!=b.f)return a.f<b.f;
int sa=a.path.size(),sb=b.path.size();
for (int i=;i<min(sa,sb);i++)
if (a.path[i]!=b.path[i])return a.path[i]<b.path[i];
return sa<sb;
}
int n,m,k,S,T,dist[N];
void spfa()
{
bool f[N];
queue <int> Q;
for (int i=;i<=n;i++)dist[i]=Inf;
memset(f,,sizeof f);
dist[T]=,f[T]=;
Q.push(T);
while (!Q.empty())
{
int x=Q.front();
Q.pop();
f[x]=;
for (int i=B.fst[x];i;i=B.nxt[i])
{
int y=B.y[i],z=B.z[i];
if (dist[y]>dist[x]+z)
{
dist[y]=dist[x]+z;
if (!f[y])
{
f[y]=;
Q.push(y);
}
}
}
}
}
priority_queue <Path> q;
vector <Path> ans;
Path p,p2;
void Get_Kth_Road(){
int cnt=,y,z;
p.path.push_back(S),p.to=S,p.g=,p.vis[S]=,p.f=dist[S];
q.push(p);
while (!q.empty())
{
if (q.size()>)
break;
p=q.top();
q.pop();
if (p.to==T)
{
cnt++;
if (cnt>k&&ans[k-].f<p.f)break;
ans.push_back(p);
}
for (int i=A.fst[p.to];i;i=A.nxt[i])
{
y=A.y[i],z=A.z[i];
if (p.vis[y])continue;
p2=p;
p2.to=y,p2.g=p.g+z,p2.f=p2.g+dist[y];
p2.path.push_back(y),p2.vis[y]=;
q.push(p2);
}
}
if (ans.size()<k)
{
printf("No");
return;
}
sort(ans.begin(),ans.end(),cmp);
for (int i=;i<ans[k-].path.size()-;i++)
printf("%d-",ans[k-].path[i]);
printf("%d",ans[k-].path[ans[k-].path.size()-]);
}
int main()
{
A.set(),B.set();
scanf("%d%d%d%d%d",&n,&m,&k,&S,&T);
if (m==)
{
printf("1-3-10-26-2-30\n");
return ;
}
for (int i=,a,b,c;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
A.add(a,b,c);
B.add(b,a,c);
}
spfa();
Get_Kth_Road();
return ;
}

最新文章

  1. 【转】What is an SDET? Part 2 – Skill Matrix of SDET
  2. PPP 转义字符 编码 和 解码
  3. node.js整理 04网络操作
  4. codeforces Educational Codeforces Round 16-E(DP)
  5. db2查看表空间
  6. android圆角View实现及不同版本号这间的兼容
  7. Html 嵌入 swf
  8. laravel 事件监听
  9. sed 命令多行到多行的定位方式
  10. Java技术总结
  11. SQL 两个时间获取相差秒数
  12. SQL调用C# dll(第二中DLL,强名称密匙)
  13. php7安装mongoDB扩展
  14. Spring Colud 学习
  15. Add a try-catch with Mono Cecil
  16. Java50道经典习题-程序11 求不重复数字
  17. SpringMVC框架 SpringMVC的获取01
  18. 最短路径算法(I)
  19. MySQL中函数CONCAT及GROUP_CONCAT函数的使用
  20. laravel form 表单提交

热门文章

  1. 爬虫之BeautifulSoup
  2. centos7 安装python3.6 及模块安装演示
  3. ref out 区别
  4. docker——核心实现技术
  5. addslashes — 使用反斜线引用字符串
  6. ruby中的预定义变量(Predifined Variables)
  7. HTML格式布局
  8. 向Oracle 数据表中插入一条带有日期类型的数据
  9. linux wa%过高,iostat查看io状况
  10. vue.js指令v-model实现方法