最短路总结（题目合集）

比眉伴天荒 2021-10-13 02:57 255阅读 0赞

## 1、HDU 6670 Mindis（建图+最短路） ##

## 题意： ##

## Description   平面上有 n 个矩形，矩形的边平行于坐标轴，现在度度熊需要操控一名角色从 A 点走到 B 点。   该角色可以上下左右移动，在恰被 k 个矩形覆盖的区域，该角色的速率为 k+1 个距离/秒（矩形覆盖区域包括边界）。 ##

## 请求出 A 移动到 B 最快需要多少秒。 ##

## Input ##

## 第一行一个整数 T (1≤T≤5) 表示数据组数。   对于每组数据，第一行输入一个整数 n (1≤n≤200)。   接下来 n 行每行 4 个整数 x1,y1,x2,y2 (0≤x1<x2≤1000000000,0≤y1<y2≤1000000000)，分别表示矩形的左下角和右上角的坐标。   最后一行四个整数 xa,ya,xb,yb ((0≤xa,xb,ya,yb≤1000000000) 代表 A 和 B 的坐标。 ##

## Output ##

## 对于每组数据，输出一个小数表示答案。答案保留 5 位小数。 ##

## Sample Input ##

## 1   1   5 5 6 6   7 7 8 8 ##

## Sample Output ##

## 2.00000 ##

## 分析：将所有坐标离散化，建网格图（400\*400），相邻两点的两点之间的距离/速度。统计每个点被多少个矩形覆盖，cntx，cnty两个数组记录水平、垂直方向上每个顶点被矩形覆盖的次数（最右端和最上端的不记录）。为什么需要分别统计呢？主要是防止两个点经过的矩形数量不一样造成的影响。画个草图就很好理解了，结合代码更好理解。然后利用优先队列+bfs（搜的时候取min，和前面对应起来）跑一遍最短路就行了。参考[https://blog.csdn.net/qq\_41879343/article/details/99706228\#comments。][https_blog.csdn.net_qq_41879343_article_details_99706228_comments] ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define inf 0x3f3f3f3f
    const int N = 1e3+5;
    int t,n,p[N][4],sx,sy,ex,ey,dx[N],dy[N],cntx[N][N],cnty[N][N],nx,ny,vis[N][N];
    int dir[4][2]={1,0,-1,0,0,-1,0,1};
    double d[N][N];
    
    struct nd {
        int x,y;
        bool operator<(const nd &a) const {
            return d[x][y]>=d[a.x][a.y];
        }
    };
    
    void solve() {
        priority_queue<nd,vector<nd>,less<nd> > pq;
        pq.push({sx,sy});
        d[sx][sy]=0;
        while(!pq.empty()) {
            nd tp = pq.top();
            pq.pop();
            if(vis[tp.x][tp.y]) continue;
            vis[tp.x][tp.y]=1;
            for(int i=0;i<4;++i) {
                int xx=tp.x+dir[i][0],yy=tp.y+dir[i][1];
                if(!xx||!yy||xx>nx||yy>ny||vis[xx][yy]) continue;
                double dis;
                if(tp.y==yy) dis=1.0*(dx[tp.x]-dx[xx])/cntx[min(tp.x,xx)][tp.y];
                else dis=1.0*(dy[tp.y]-dy[yy])/cnty[tp.x][min(tp.y,yy)];
                if(dis<0) dis=-dis;
                if(d[tp.x][tp.y]+dis<d[xx][yy]) {
                    d[xx][yy]=d[tp.x][tp.y]+dis;
                    pq.push({xx,yy});
                }
            }
        }
        printf("%.5f\n",d[ex][ey]);
    }
    
    int main(){
        scanf("%d",&t);
        while(t--) {
            scanf("%d",&n);
            nx=0,ny=0;
            for(int i=1;i<=n;i++) {
                scanf("%d%d%d%d",&p[i][0],&p[i][1],&p[i][2],&p[i][3]);
                dx[++nx]=p[i][0],dx[++nx]=p[i][2];
                dy[++ny]=p[i][1],dy[++ny]=p[i][3];
            }
            scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
            dx[++nx]=sx,dx[++nx]=ex;
            dy[++ny]=sy,dy[++ny]=ey;
            sort(dx+1,dx+nx+1);
            sort(dy+1,dy+ny+1);
            nx = unique(dx+1,dx+nx+1)-dx-1;
            ny = unique(dy+1,dy+ny+1)-dy-1;
            for(int i=1;i<=nx;i++)
                for(int j=1;j<=ny;j++)
                    cntx[i][j]=cnty[i][j]=1;//初始化为1
            for(int i=1;i<=n;i++) {
                p[i][0]=lower_bound(dx+1,dx+1+nx,p[i][0])-dx;
                p[i][1]=lower_bound(dy+1,dy+1+ny,p[i][1])-dy;
                p[i][2]=lower_bound(dx+1,dx+1+nx,p[i][2])-dx;
                p[i][3]=lower_bound(dy+1,dy+1+ny,p[i][3])-dy;
                for(int j=p[i][0];j<p[i][2];++j)///记录水平方向矩形覆盖次数+1
                    for(int k=p[i][1];k<=p[i][3];++k)
                        cntx[j][k]++;
                for(int j=p[i][0];j<=p[i][2];++j)///记录垂直方向矩形覆盖次数+1
                    for(int k=p[i][1];k<p[i][3];++k)
                        cnty[j][k]++;
            }
            for(int i=1;i<=nx;i++)
                for(int j=1;j<=ny;j++)
                    d[i][j]=inf;
            memset(vis,0,sizeof(vis));
            sx = lower_bound(dx+1,dx+1+nx,sx) - dx;
            sy = lower_bound(dy+1,dy+1+ny,sy) - dy;
            ex = lower_bound(dx+1,dx+1+nx,ex) - dx;
            ey = lower_bound(dy+1,dy+1+ny,ey) - dy;
            solve();
        }
    	return 0;
    }

## 2、HDU 6714 最短路 2 ##

## 题意：[中文题][Link 1] ##

## 分析：开始一直想着Floyd会超时，后面才知道用优化后的Floyd就能过，注意重边，边权取最小，对最短路的理解不够深刻啊，关于Floyd的优化可以参考[https://blog.csdn.net/lanshuizhiyun/article/details/77864648][https_blog.csdn.net_lanshuizhiyun_article_details_77864648]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e3+5;
    const ll inf = 2e18;
    const ll mod = 998244353;
    int t,n,m,u,v,w;
    ll d[N][N],s[N][N],ans;
    
    void floyd() {
        for(int k=1;k<=n;k++) {
            for(int i=1;i<=n;i++) {
                if(d[i][k]!=inf) { ///跳过不存在的路径
                    for(int j=1;j<=i;j++) { ///利用矩阵的对称性
                        if(d[i][k]+d[k][j]<d[i][j]) {
                            d[i][j]=d[j][i]=d[i][k]+d[k][j];
                            s[i][j]=s[j][i]=max(s[i][j],1LL*k);
                        }
                    }
                }
            }
        }
    }
    
    int main() {
        scanf("%d",&t);
        while(t--) {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    s[i][j]=0;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(i==j) d[i][j]=0;
                    else d[i][j]=inf;
            for(int i=1;i<=m;i++) {
                scanf("%d%d%d",&u,&v,&w);
                d[u][v]=d[v][u]=min(d[u][v],1LL*w);
            }
            floyd();
            ll ans=0;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    ( ans += s[i][j]) %= mod;
            cout<<ans<<endl;
        }
    	return 0;
    }

[https_blog.csdn.net_qq_41879343_article_details_99706228_comments]: https://blog.csdn.net/qq_41879343/article/details/99706228#comments
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20211013/c5dfb107b81c49709a2e8c9f28efa50a.png
[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6714
[https_blog.csdn.net_lanshuizhiyun_article_details_77864648]: https://blog.csdn.net/lanshuizhiyun/article/details/77864648