https://acm.taifua.com/archives/jsk31445.html

链接:

https://nanti.jisuanke.com/t/31445

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = ;
const int inf = 0x3f3f3f3f;
int n, m, s, t, k, Time;
bool vis[maxn];
int dist[maxn]; struct Node
{
int v, c;
Node (int _v = , int _c = ): v(_v), c(_c) {}
bool operator < (const Node &rhs) const
{
return c + dist[v] > rhs.c + dist[rhs.v]; // 估价函数 fx = gx + hx 路径短先出队
}
}; struct Edge
{
int to, cost;
Edge (int _to = , int _cost = ): to(_to), cost(_cost) {}
}; vector <Edge> E[maxn], revE[maxn]; void addedge(int u, int v, int w)
{
E[v].push_back(Edge(u, w)); // 反向加边
revE[u].push_back(Edge(v, w)); // 正向加边
} void dijkstra(int s, int n) // 最短路
{
for (int i = ; i <= n; ++i)
{
vis[i] = false;
dist[i] = inf;
}
dist[s] = ;
priority_queue <Node> Q;
Q.push(Node(s, dist[s]));
while (!Q.empty())
{
Node tmp = Q.top();
Q.pop();
int u = tmp.v;
if (vis[u])
continue;
vis[u] = true;
for (int i = ; i < E[u].size(); ++i)
{
int v = E[u][i].to, cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost)
{
dist[v] = dist[u] + cost;
Q.push(Node(v, dist[v]));
}
}
}
} int astar(int s)
{
if (dist[s] == inf) // 不能到达
return -;
priority_queue <Node> Q;
Q.push(Node(s, ));
k--;
while (!Q.empty())
{
Node tmp = Q.top();
Q.pop();
int u = tmp.v;
if (tmp.c + dist[u] > Time) // 超时直接返回-1,可不要
return -;
if (u == t)
{
if (k)
--k;
else // 第k次到达目标节点t
return tmp.c;
}
for (int i = ; i < revE[u].size(); ++i)
{
int v = revE[u][i].to, cost = revE[u][i].cost;
Q.push(Node(v, tmp.c + cost));
}
}
return -;
} int main()
{
int u, v, w;
while (scanf("%d%d", &n, &m) != EOF)
{
scanf("%d%d%d%d", &s, &t, &k, &Time);
for (int i = ; i <= n; ++i)
{
E[i].clear();
revE[i].clear();
}
for (int i = ; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
}
dijkstra(t, n); // t点到所有点的最短路
int ans = astar(s);
if (ans == - || ans > Time) // 无法到达或者超过时间
printf("Whitesnake!\n");
else
printf("yareyaredawa\n");
}
return ;
}

最新文章

  1. 使用TSQL查询和更新 JSON 数据
  2. UART
  3. Codeforces Round #383 (Div. 2) A,B,C,D 循环节,标记,暴力,并查集+分组背包
  4. 使用DotNetOpenAuth搭建OAuth2.0授权框架——Demo代码简单说明
  5. 项目部署之VPN+端口映射
  6. C++对象创建与释放
  7. 我的PHP之旅--认识数据库及数据库操作
  8. apache301重定向设置
  9. 2015 8月之后&quot;云计算&quot;学习计划
  10. Behavioral模式之Observer模式
  11. Python学习日记:day4
  12. java中的左右移
  13. 用VSCode开发一个基于asp.net core 2.0/sql server linux(docker)/ng5/bs4的项目(2)
  14. Unity C#笔记 协程
  15. 【转】SpringBoot启动服务的三种方式
  16. 利用PIL和Selenium实现页面元素截图
  17. input元素的required属性引发的血案
  18. Android开发——adb连接夜神模拟器
  19. top高级技能
  20. VC++调用MSFlexGrid的SetRow方法,出现异常“Invalid Row Value”

热门文章

  1. 各种安卓模拟器连接Adb
  2. 字节码技术---------动态代理,lombok插件底层原理。类加载器
  3. 数据结构之Hyperloglog
  4. laravel-mix 热重载404的问题
  5. MVC 知识点总结
  6. 部署WebService服务碰到的一个小问题
  7. Java常用函数式接口--Consumer接口andThen()方法使用案例(二)
  8. IO(File、递归)
  9. codevs 4888 零件分组
  10. SqlServer 填充因子的说明