最短路--Dijkstra&&Floyed&&SPFA

最短路径是一个很常见的问题，这里有3种方法，可供参考。

一.Dijkstra
#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int a[][];

double c[];

bool b[];

double f[][];

int n,i,j,k,x,y,m,s,e;

double minl;

double maxx = 1e30;

int main()

{

    cin >> n;

    for (i = ; i <= n; i++)

        cin >> a[i][] >> a[i][];

    for (i = ; i <= n; i++)

        for(j = ; j <= n; j++)

            f[i][j] = maxx;

    cin >> m;

    for (i = ; i <= m; i++)

    {

        cin >> x >> y;

        f[x][y] = f[y][x] = sqrt(pow(double(a[x][]-a[y][]),)+pow(double(a[x][]-a[y][]),));

    }

    cin>>s>>e;

    for(int i = ;i <= n;i++)

    {

        c[i] = f[s][i];

    }

    memset(b,false,sizeof(b));

    b[s] = true;

    c[s] = ;

    for(int i = ;i <= n;i++)

    {

        minl = maxx;

        k = ;

        for(int j = ;j <= n;j++)

        {

            if(b[j] == false && c[j] < minl)//没走过的路程最小的点

            {

                minl = c[j];

                k = j;

            }

        }

        if(k == )

        break;

        b[k] = true;

        for(int j = ;j <= n;j++)  //将所以能变的点最小路程全变了

        {

            if(c[k] + f[k][j] < c[j])

            c[j] = c[k] + f[k][j];

        }

    }

    printf("%.2lf",c[e]);

    return ;

}

二.Floyed
#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

double f[][];

int a[][];

int m,n,x,y,r,s,e;

int main()

{

    memset(f,,sizeof(f));

    cin>>n;

    for(int i = ;i <= n;i++)

    {

        cin>>a[i][]>>a[i][];

    }

    cin>>m;

    for(int i = ;i <= m;i++)

    {

        cin>>x>>y;

        f[y][x] = f[x][y] = sqrt(pow(double(a[x][]-a[y][]),)+pow(double(a[x][]-a[y][]),));

    }

    cin>>s>>e;

    for(int k = ;k <= n;k++)

    {

        for(int i = ;i <= n;i++)

        {

            for(int j = ;j <= n;j++)

            {

                if(f[i][j] > f[i][k] + f[k][j] && i != j && i != k && j != k)

                f[i][j] = f[i][k] + f[k][j];

            }

        }

    }

    printf("%.2lf",f[s][e]);

    return ;

}

/*

5

0 0

2 0

2 2

0 2

3 1

5

1 2

1 3

1 4

2 5

3 5

1 5

*/

三.SPFA

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int n,p,c,i,j,x,y,t,min1,head,tail,tot,u;

int a[][],b[],dis[],num[],w[][];

queue <int> team;

bool exist[];

int main()

{

    cin>>n>>p>>c;

    for(i=;i<=p;i++)

    {

        b[i]=;

        num[i]=;

        for(j=;j<=p;j++)

            w[i][j]=0x7fffffff/;

    }

    for(i = ;i <= n;i++)

        cin>>b[i];

    for(i=;i<=c;i++)                                      //邻接矩阵存储

    {

        cin>>x>>y>>t;

        w[x][y] = t;

        a[x][++num[x]] = y;

        a[y][++num[y]] = x;

        w[y][x] = w[x][y];

    }

    min1=0x7fffffff/;

    for(i=;i<=p;i++)

    {

        for(j=;j<=p;j++) dis[j]=0x7fffffff/;                      //队列数组初始化

        memset(exist,false,sizeof(exist));                   //exist标志初始化

        dis[i]=;

        exist[i]=true;

        team.push(i);

        while(!team.empty())

        {

            u = team.front();

            team.pop();

            exist[u] = true;

            for(int j = ;j <= num[u];j++)

            {

                if(dis[a[u][j]] > dis[u] + w[u][a[u][j]])

                {

                    dis[a[u][j]] = dis[u] + w[u][a[u][j]];

                    if(!exist[a[u][j]])

                    {

                        team.push(a[u][j]);

                        a[u][j] = true;

                    }

                }

            }

        }

        tot=;

        for(j=;j<=n;j++)

        tot+=dis[b[j]];

        if (tot<min1) min1=tot;

    }

    cout<<min1;

    return ;

}