图论最短路径例题

一本通网站上不去,截图为证

图论最短路径例题

还是要整博客的。。。

目前学了FloydO(n3)和dijkstra算法O(n2

Floyd是把每个点都遍历一遍,而后者只针对单个起点所以前者慢,但前者可以处理负边权(边的长度)。

下面是一道例题(数据较小用了Floyd):

中山路上有n(n<=100)家店,每家店的坐标均在-10000~10000之间。其中的m家店之间有通路。若有通路,则表示可以从一家店走到另一家店,通路的距离为两点间的直线距离。现在要找出从一家店到另一家店之间的最短距离。

代码:

#include<bits/stdc++.h>
using namespace std;
int a[105][3];
double f[105][105];
int n,i,j,k,x,y,m,s,e;
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&a[i][1],&a[i][2]);
    scanf("%d",&m);
    memset(f,0x7f,sizeof(f));  //附一个超大的值,方便下面考虑最短路径
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        f[x][y]=(sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2)));  //计算边权,也可以写成函数
        f[y][x]=f[x][y];
    }
    scanf("%d%d",&s,&e);
    for(k=1;k<=n;k++){
        for(i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if((i!=j)&&(j!=k)&&(i!=k)&&(f[i][k]+f[k][j]<f[i][j]))   //Floyd主要部分,遍历每个结点之间的最短路径,将k视为中间节点
                f[i][j]=f[i][k]+f[k][j];
            }
        }
    }
    printf("%0.2lf",f[s][e]);
    return 0;
}

整个就是模板题,主要用来熟练思路

上一篇:C - Anna, Svyatoslav and Maps floyd


下一篇:P1744 采购特价商品