首页 > 其他 > 详细

hdu2544-最短路

时间:2015-03-21 14:03:35      阅读:355      评论:0      收藏:0      [点我收藏+]

本题地址:(http://acm.hdu.edu.cn/showproblem.php?pid=2544)
本题使用的是Dijkstra算法,这种算法的时间复杂度为O(V*V),使用这种前提—>是图没有负权值边,不然这种算法就无法解决问题,还得使用Bellman-Ford算法(使用这种算法的前提是图中不存在负圈:从源点可达的总权值为负的回路)

AC代码如下:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=111;
const int inf=201314;
int n,m,cost[maxn][maxn],vis[maxn],dis[maxn];
void init()
{
    memset(cost,0,sizeof(cost));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i!=j)
                cost[i][j]=inf;
}
void dijkstra()
{
    memset(vis,false,sizeof(vis));
    for(int i=1; i<=n; i++)
        dis[i]=cost[1][i];
    vis[1]=true;
    for(int i=1; i<=n; i++)
    {
        int mins=inf,pos=1;
        for(int j=1; j<=n; j++)
            if(!vis[j]&&dis[j]<mins)
                mins=dis[pos=j];
        vis[pos]=true;
        for(int k=1; k<=n; k++)
            if(!vis[k]&&dis[k]>dis[pos]+cost[pos][k])
                dis[k]=dis[pos]+cost[pos][k];
    }
}
int main()
{
    while(cin>>n>>m&&(m+n))
    {
        init();
        for(int i=0; i<m; i++)
        {
            int from,to,co;
            cin>>from>>to>>co;
            if(co<cost[from][to])
                cost[from][to]=cost[to][from]=co;
        }
        dijkstra();
        cout<<dis[n]<<endl;
    }
    return 0;
}

hdu2544-最短路

原文:http://blog.csdn.net/u014004096/article/details/44515151

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!