POJ 2387 Til the Cows Come Home --最短路模板题

时间：2020-11-30 14:57:57

Dijkstra模板题，也可以用Floyd算法。

关于Dijkstra算法有两种写法，只有一点细节不同，思想是一样的。

写法1：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#define Mod 1000000007

using namespace std;

#define N 1007

int mp[N][N],n,m;

int dis[N],vis[N];

void Dijastra(int s)

{

    int now = s;

    int i,k;

    dis[now] = ;

    vis[now] = ;

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

    {

        for(k=;k<=n;k++)  //order 1

        {

            if(mp[now][k] != Mod && dis[now] + mp[now][k] < dis[k])

                dis[k] = dis[now] + mp[now][k];

        }

        int mini = Mod;   //order 2

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

        {

            if(dis[k] < mini && !vis[k])

            {

                now = k;

                mini = dis[k];

            }

        }

        vis[now] = ;

    }

}

int main()

{

    int u,v,w,i,j;

    while(scanf("%d%d",&m,&n)!=EOF)

    {

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

            dis[i] = Mod;

        dis[] = ;

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

        {

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

                mp[i][j] = Mod;

            mp[i][i] = ;

        }

        while(m--)

        {

            scanf("%d%d%d",&u,&v,&w);

            if(w < mp[u][v])

                mp[u][v] = mp[v][u] = w;

        }

        memset(vis,,sizeof(vis));

        Dijastra();

        printf("%d\n",dis[n]);

    }

    return ;

}

写法2：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#define Mod 1000000007

using namespace std;

#define N 1007

int mp[N][N],n,m;

int dis[N],vis[N];

void Dijastra(int s)

{

    int now;

    int i,k;

    dis[s] = ;

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

    {

        int mini = Mod;  //order 1

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

        {

            if(dis[k] < mini && !vis[k])

            {

                now = k;

                mini = dis[k];

            }

        }

        vis[now] = ;

        for(k=;k<=n;k++)  //order 2

        {

            if(mp[now][k] != Mod && dis[now] + mp[now][k] < dis[k])

                dis[k] = dis[now] + mp[now][k];

        }

    }

}

int main()

{

    int u,v,w,i,j;

    while(scanf("%d%d",&m,&n)!=EOF)

    {

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

            dis[i] = Mod;

        dis[] = ;

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

        {

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

                mp[i][j] = Mod;

            mp[i][i] = ;

        }

        while(m--)

        {

            scanf("%d%d%d",&u,&v,&w);

            if(w < mp[u][v])

                mp[u][v] = mp[v][u] = w;

        }

        memset(vis,,sizeof(vis));

        Dijastra();

        printf("%d\n",dis[n]);

    }

    return ;

}

相关文章