POJ 2502 最短路

﹏ヽ暗。殇╰゛Y 2023-08-17 16:37 221阅读 0赞

题意略。

思路：

本题有必要记录一下。首先是dijkstra求最短路没问题，关键是在建图的时候，地铁沿线还要加上行走互达的边，因为：

1161042-20190819192821981-355754209.png

在本图中，AC之间的最短时间有可能不是A->B->C这么走，而是有可能从A走到C，这个地方没有考虑周全，wa了几发。

代码如下：

堆优化版：

  1. 1 #include<iostream>
  2.   2 #include<algorithm>
  3.   3 #include<cstdio>
  4.   4 #include<cstring>
  5.   5 #include<cmath>
  6.   6 #include<vector>
  7.   7 #include<queue>
  8.   8 using namespace std;
  9.   9 const int maxn = 255;
  10.  10 const int INF = 0x3f3f3f3f;
  11.  11 const double eps = 1e-6;
  12.  12 
  13.  13 struct edge{
  14.  14     int to;
  15.  15     double cost;
  16.  16     edge(int to = 0,double cost = 0){
  17.  17         this->to = to,this->cost = cost;
  18.  18     }
  19.  19 };
  20.  20 struct Point{
  21.  21     double x,y;
  22.  22     Point(double x = 0,double y = 0){
  23.  23         this->x = x,this->y = y;
  24.  24     }
  25.  25 };
  26.  26 struct node{
  27.  27     int v;
  28.  28     double c;
  29.  29     node(int v = 0,double c = 0){
  30.  30         this->v = v,this->c = c;
  31.  31     }
  32.  32 };
  33.  33 struct cmp{
  34.  34     bool operator() (const node& n1,const node& n2){
  35.  35         return n1.c > n2.c;
  36.  36     }
  37.  37 };
  38.  38 
  39.  39 bool vis[maxn];
  40.  40 double dist[maxn];
  41.  41 vector<edge> graph[maxn];
  42.  42 priority_queue<node,vector<node>,cmp> que;
  43.  43 Point st,ed,store[maxn];
  44.  44 int tail = 0;
  45.  45 
  46.  46 double calDist(Point p1,Point p2,bool signal){
  47.  47     double dx = p1.x - p2.x;
  48.  48     double dy = p1.y - p2.y;
  49.  49     double len = sqrt(dx * dx + dy * dy);
  50.  50     len /= 1000.0;
  51.  51     double denominator = signal ? 40.0 : 10.0;
  52.  52     double ret = len / denominator;
  53.  53     ret *= 60.0;
  54.  54     return ret;
  55.  55 }
  56.  56 int sgn(double x){
  57.  57     if(fabs(x) < eps) return 0;
  58.  58     else if(x > 0) return 1;
  59.  59     return -1;
  60.  60 }
  61.  61 int dijkstra(){
  62.  62     while(que.size()) que.pop();
  63.  63     for(int i = 0;i < tail;++i) dist[i] = INF;
  64.  64     memset(vis,false,sizeof(vis));
  65.  65     dist[0] = 0;
  66.  66     int idx = tail - 1;
  67.  67     que.push(node(0,0));
  68.  68     while(que.size()){
  69.  69         node temp = que.top();
  70.  70         que.pop();
  71.  71         int v = temp.v;
  72.  72         if(vis[v]) continue;
  73.  73         vis[v] = true;
  74.  74         for(int i = 0;i < graph[v].size();++i){
  75.  75             edge e = graph[v][i];
  76.  76             int to = e.to;
  77.  77             double cost = e.cost;
  78.  78             if(vis[to] || sgn(dist[to] - cost - dist[v]) <= 0) continue;
  79.  79             dist[to] = cost + dist[v];
  80.  80             que.push(node(to,dist[to]));
  81.  81         }
  82.  82     }
  83.  83     int ret = int(dist[idx] + 0.5);
  84.  84     return ret;
  85.  85 }
  86.  86 bool Read(){
  87.  87     double x,y;
  88.  88     bool jud = (scanf("%lf%lf",&x,&y) == 2);
  89.  89     if(!jud) return false;
  90.  90     store[tail++] = Point(x,y);
  91.  91     while(scanf("%lf%lf",&x,&y) == 2 && sgn(x + 1) != 0){
  92.  92         store[tail++] = Point(x,y);
  93.  93     }
  94.  94     return true;
  95.  95 }
  96.  96 void add_e(int from,int to,bool signal){
  97.  97     double cost = calDist(store[from],store[to],signal);
  98.  98     graph[from].push_back(edge(to,cost));
  99.  99     graph[to].push_back(edge(from,cost));
  100. 100 }
  101. 101 
  102. 102 int main(){
  103. 103     scanf("%lf%lf%lf%lf",&st.x,&st.y,&ed.x,&ed.y);
  104. 104     store[tail++] = st;
  105. 105     int keep = tail;
  106. 106     while(Read()){
  107. 107         for(int i = keep;i < tail - 1;++i){
  108. 108             add_e(i,i + 1,true);
  109. 109         }
  110. 110         for(int i = keep;i < tail;++i)
  111. 111             for(int j = 0;j < i;++j)
  112. 112                 add_e(i,j,false);
  113. 113         keep = tail;
  114. 114     }
  115. 115     store[tail++] = ed;
  116. 116     int idx = tail - 1;
  117. 117     for(int i = 0;i < idx;++i) add_e(idx,i,false);
  118. 118     int ans = dijkstra();
  119. 119     printf("%d\n",ans);
  120. 120     return 0;
  121. 121 }

普通Dijkstra:

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<vector>
  6. #include<cmath>
  7. using namespace std;
  8. const int maxn = 255;
  9. const double v1 = 10000;
  10. const double v2 = 40000;
  11. const double INF = 0x3f3f3f3f;
  12. const double eps = 1e-6;
  14. struct edge{
  15.     int to;
  16.     double cost;
  17.     edge(int to,double cost = 0){
  18.         this->to = to,this->cost = cost;
  19.     }
  20. };
  21. struct Point{
  22.     double x,y;
  23.     Point(double x = 0,double y = 0){
  24.         this->x = x,this->y = y;
  25.     }
  26. };
  28. Point store[maxn],st,ed;
  29. vector<edge> graph[maxn];
  30. double dist[maxn];
  31. bool vis[maxn];
  32. int tail = 0;
  34. int sgn(double x){
  35.     if(fabs(x) < eps) return 0;
  36.     else if(x > 0) return 1;
  37.     return -1;
  38. }
  39. double calDist(Point p1,Point p2){
  40.     double dx = p1.x - p2.x;
  41.     double dy = p1.y - p2.y;
  42.     return sqrt(dx * dx + dy * dy);
  43. }
  44. void add_e(int from,int to,double cost){
  45.     graph[from].push_back(edge(to,cost));
  46.     graph[to].push_back(edge(from,cost));
  47. }
  48. int Dijkstra(){
  49.     for(int i = 0;i < tail;++i){
  50.         vis[i] = false;
  51.         dist[i] = INF;
  52.     }
  53.     int cnt = tail;
  54.     dist[0] = 0;
  55.     while(cnt > 0){
  56.         int idx = -1;
  57.         for(int i = 0;i < tail;++i){
  58.             if(vis[i]) continue;
  59.             if(idx == -1 || sgn(dist[idx] - dist[i]) > 0) idx = i;
  60.         }
  61.         vis[idx] = true;
  62.         --cnt;
  63.         for(int i = 0;i < graph[idx].size();++i){
  64.             edge e = graph[idx][i];
  65.             int to = e.to;
  66.             double cost = e.cost;
  67.             if(vis[to] || sgn(dist[to] - dist[idx] - cost) <= 0) continue;
  68.             dist[to] = dist[idx] + cost;
  69.         }
  70.     }
  71.     int ret = int(dist[tail - 1] + 0.5);
  72.     return ret;
  73. }
  74. bool Read(){
  75.     double x,y;
  76.     bool jud = (scanf("%lf%lf",&x,&y) == 2);
  77.     if(!jud) return false;
  78.     store[tail++] = Point(x,y);
  79.     while(scanf("%lf%lf",&x,&y) == 2 && sgn(x + 1) != 0){
  80.         store[tail++] = Point(x,y);
  81.     }
  82.     return true;
  83. } 
  85. int main(){
  86.     scanf("%lf%lf%lf%lf",&st.x,&st.y,&ed.x,&ed.y);
  87.     tail = 0;
  88.     store[tail++] = st;
  89.     int keep = tail;
  90.     while(Read()){
  91.         for(int i = keep;i < tail - 1;++i){
  92.             double c = calDist(store[i],store[i + 1]) / v2 * 60.0;
  93.             add_e(i,i + 1,c);
  94.         }
  95.         for(int i = keep;i < tail;++i){
  96.             for(int j = 0;j < i;++j){
  97.                 double c = calDist(store[i],store[j]) / v1 * 60.0;
  98.                 add_e(i,j,c);
  99.             }
  100.         }
  101.         keep = tail;
  102.     }
  103.     store[tail++] = ed;
  104.     int idx = tail - 1;
  105.     for(int i = 0;i < idx;++i){
  106.         double c = calDist(store[idx],store[i]) / v1 * 60.0;
  107.         add_e(idx,i,c);
  108.     }
  109.     int ans = Dijkstra();
  110.     printf("%d\n",ans);
  111.     return 0;
  112. }

转载于:https://www.cnblogs.com/tiberius/p/11379153.html

发表评论

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

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

相关阅读

    相关 最短路

    队列+松弛操作 读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d\[v\]变小），那么就更新，另外，如果

    忘是亡心i忘是亡心i/ 0 赞/ 300 阅读

    相关 最短路

    一下模板均已通过HDUOJ 2544 程序设计竞赛队空间和时间复杂度要求都很高，所以朴素的Dijkstra[算法][Link 1]无论时间还是空间，效率都很低。 所以，一般

    淡淡的烟草味﹌淡淡的烟草味﹌/ 0 赞/ 362 阅读

    相关 最短路

    最短路 典型用途：交通网络的问题——从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？ 交通网络用有向网来表示：顶点——表示城市，弧——表示两个城

    淡淡的烟草味﹌淡淡的烟草味﹌/ 0 赞/ 341 阅读