hdu2544 迪杰斯特拉题目优化

迪杰斯特拉的用法不多讲，详见点击打开链接。

下面两个代码：

这个是用邻接矩阵存图的迪杰斯特拉。

#include<stdio.h>

int main()

{

    int e[1005][1005],dis[1005],book[1005],i,j,n,m,t1,t2,t3,u,v,min;

    int inf=9999999;

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

    {

        if(m==n&&n==0) return 0;

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

        {

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

            {

                if(i==j) e[i][j]=0;

                else e[i][j]=inf;

            }

        }

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

        {

            scanf("%d%d%d",&t1,&t2,&t3);

            e[t1][t2]=e[t2][t1]=t3;

        }

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

        {

            dis[i]=e[1][i];

        }

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

        {

            book[i]=0;

        }

        book[1]=1;

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

        {

            min=inf;

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

            {

                if(book[j]==0&&dis[j]<min)

                {

                    min=dis[j];

                    u=j;

                }

            }

            book[u]=1;

            for(v=1; v<=n; v++)

            {

                if(e[u][v]<inf)

                    if(dis[v]>dis[u]+e[u][v])

                        dis[v]=dis[u]+e[u][v];

            }

        }

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

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

    }

    return 0;

}

用数组模拟邻接表的迪杰斯特拉：数组模拟邻接表详见点击打开链接

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

#define MAX_SIZE 10005

const int INF=2e9+1e8;

int start[MAX_SIZE],terminal[MAX_SIZE],value[MAX_SIZE];

int first[MAX_SIZE],nexts[MAX_SIZE],dis[MAX_SIZE],vis[MAX_SIZE];

int main()

{

    int n,m,i,j,minn,k;

    while(scanf("%d %d",&n,&m)!=EOF) //  n个点m条边

    {

        if(n==m&&m==0) return 0;

        for(i=1; i<=n; i++)  // 初始化 first 数组

            first[i]=-1;

        for(i=1; i<=m; i++) //  存入m条边

        {

            int ss,ee,vv;

            scanf("%d %d %d",&ss,&ee,&vv);

            start[i*2-1]=ss,terminal[i*2-1]=ee,value[i*2-1]=vv;

            nexts[i*2-1]=first[start[i*2-1]];

            first[start[i*2-1]]=i*2-1;

            start[i*2]=ee,terminal[i*2]=ss,value[i*2]=vv;

            nexts[i*2]=first[start[i*2]];

            first[start[i*2]]=i*2;

        }

        // 初始化 dis 数组

        k=first[1];

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

            dis[i]=INF;

        while(k!=-1)

        {

            dis[terminal[k]]=value[k];

            k=nexts[k];

        }

        memset(vis,0,sizeof(vis)); // 标记当前位置是否来过   0 表示还没有来过

        vis[1]=1;

        int mid_pos;

        int times=n-1;

        // 迪杰斯特拉 核心代码

        while(times--)

        {

            minn=INF;

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

            {

                if(vis[j]==0&&dis[j]<minn)

                {

                    minn=dis[j];

                    mid_pos=j;

                }

            }

            if(minn==INF) continue;

            vis[mid_pos]=1;

            //  遍历 pos 点能到的地方

            k=first[mid_pos];

            while(k!=-1)

            {

                if(dis[mid_pos]+value[k]<dis[terminal[k]]) dis[terminal[k]]=dis[mid_pos]+value[k];

                k=nexts[k];

            }

        }

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

//            printf("%d ",dis[i]);

//        printf("\n");

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

    }

    return 0;

}

巴特西

hdu2544 迪杰斯特拉题目优化

最新文章

热门文章