最短路径？青蛙(Frogger), ZOJ1942, POJ2253

朴灿烈づ我的快乐病毒、 2024-02-17 23:47 147阅读 0赞

感觉只是用了最短路径的思想啊。

bellman算法是神奇的迭代，dijkstra是神奇的贪心。

看了下面这个图，感到这特么就是个最小生成树的计算过程啊。

Center 

  1. //本题求的是从起点到终点的所有通路中的最大的边的最小值（起点是第一个，终点是第二个坐标）,感觉和最短路没有太大的关系，就是过程有点类似  
  2. //请尽量选择c++编译器，g++神奇的wa 
  3. #include<cstdio>
  4. #include<iostream>
  5. #include<cstring>
  6. #include<cmath>
  7. #include<queue>
  8. #include<limits.h> 
  9. using namespace std;
  10. const int mn=201,mm=40005;
  11. struct Edge{
  12.     int to,w,next;
  13. }edges[mm];
  14. int head[mn],n,tot,x[mn],y[mn];
  15. inline int dist(int i,int j){
  16.     return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
  17. }
  18. void add(int u,int v)
  19. {//建双向边 
  20.     edges[tot].to=v;
  21.     edges[tot].w=d

发表评论

表情：
评论列表 （有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

    相关 POJ2253 Frogger(Floyd)

    题目描述：青蛙A要找青蛙B，路径任选，求所有可能路径中跳的最远的一步，它们之中的最小距离值。 输入要求，第一行为石头数，二三行为起点和终点位置，n-2行为其他石头结点。第一

    ╰半橙微兮°╰半橙微兮°/ 0 赞/ 207 阅读