POJ 2502 最短路

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

题意略。

思路：

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

![1161042-20190819192821981-355754209.png][]

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

代码如下：

堆优化版：

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

普通Dijkstra:

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<vector>
    #include<cmath>
    using namespace std;
    const int maxn = 255;
    const double v1 = 10000;
    const double v2 = 40000;
    const double INF = 0x3f3f3f3f;
    const double eps = 1e-6;
    
    struct edge{
        int to;
        double cost;
        edge(int to,double cost = 0){
            this->to = to,this->cost = cost;
        }
    };
    struct Point{
        double x,y;
        Point(double x = 0,double y = 0){
            this->x = x,this->y = y;
        }
    };
    
    Point store[maxn],st,ed;
    vector<edge> graph[maxn];
    double dist[maxn];
    bool vis[maxn];
    int tail = 0;
    
    int sgn(double x){
        if(fabs(x) < eps) return 0;
        else if(x > 0) return 1;
        return -1;
    }
    double calDist(Point p1,Point p2){
        double dx = p1.x - p2.x;
        double dy = p1.y - p2.y;
        return sqrt(dx * dx + dy * dy);
    }
    void add_e(int from,int to,double cost){
        graph[from].push_back(edge(to,cost));
        graph[to].push_back(edge(from,cost));
    }
    int Dijkstra(){
        for(int i = 0;i < tail;++i){
            vis[i] = false;
            dist[i] = INF;
        }
        int cnt = tail;
        dist[0] = 0;
        while(cnt > 0){
            int idx = -1;
            for(int i = 0;i < tail;++i){
                if(vis[i]) continue;
                if(idx == -1 || sgn(dist[idx] - dist[i]) > 0) idx = i;
            }
            vis[idx] = true;
            --cnt;
            for(int i = 0;i < graph[idx].size();++i){
                edge e = graph[idx][i];
                int to = e.to;
                double cost = e.cost;
                if(vis[to] || sgn(dist[to] - dist[idx] - cost) <= 0) continue;
                dist[to] = dist[idx] + cost;
            }
        }
        int ret = int(dist[tail - 1] + 0.5);
        return ret;
    }
    bool Read(){
        double x,y;
        bool jud = (scanf("%lf%lf",&x,&y) == 2);
        if(!jud) return false;
        store[tail++] = Point(x,y);
        while(scanf("%lf%lf",&x,&y) == 2 && sgn(x + 1) != 0){
            store[tail++] = Point(x,y);
        }
        return true;
    } 
    
    int main(){
        scanf("%lf%lf%lf%lf",&st.x,&st.y,&ed.x,&ed.y);
        tail = 0;
        store[tail++] = st;
        int keep = tail;
        while(Read()){
            for(int i = keep;i < tail - 1;++i){
                double c = calDist(store[i],store[i + 1]) / v2 * 60.0;
                add_e(i,i + 1,c);
            }
            for(int i = keep;i < tail;++i){
                for(int j = 0;j < i;++j){
                    double c = calDist(store[i],store[j]) / v1 * 60.0;
                    add_e(i,j,c);
                }
            }
            keep = tail;
        }
        store[tail++] = ed;
        int idx = tail - 1;
        for(int i = 0;i < idx;++i){
            double c = calDist(store[idx],store[i]) / v1 * 60.0;
            add_e(idx,i,c);
        }
        int ans = Dijkstra();
        printf("%d\n",ans);
        return 0;
    }

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

[1161042-20190819192821981-355754209.png]: /images/20230810/937e366f432d48aca80ffd034e9b6fe1.png