注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj2387Til the Cows Come Home  

2014-04-12 14:09:46|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                 送牛回家
                                          BY   LGS
题目大意:T条有向路,N个点。求最短路

题解:dijk

总结:最短路。
  • Source Code
  • #include<cstdio>
    #include<cstring>
    #define maxx 99999999
    using namespace std;
    int flag,max,i,j,n,k,m,x,y,z,f[1001][1001],dis[1001];
    bool b[1001];
    int min(int a,int b){return (a>b)?b:a;}
    int main()
    {
    while (scanf("%d%d",&m,&n)!=EOF){
                  memset(b,false,sizeof(b));
     for (i=1;i<=n;i++)
     for (j=1;j<=n;j++) f[i][j]=maxx;
     for (i=1;i<=m;i++)
         {
         scanf("%d%d%d",&x,&y,&z);
         f[y][x]=min(f[y][x],z);
         f[x][y]=min(f[y][x],f[x][y]);
         }
    for (i=1;i<=n-1;i++) dis[i]=maxx;dis[n]=0;
    while (1)
        {
        flag=0;max=maxx;
        for (j=1;j<=n;j++)
          if ((dis[j]<max)&&(!b[j]))
          {max=dis[j];flag=j;}
        if (flag==0) break;
        b[flag]=true;
        for (j=1;j<=n;j++)if (j!=flag)
              if (f[flag][j]!=maxx)
          dis[j]=min(dis[j],dis[flag]+f[flag][j]);
        }
    printf("%d\n",dis[1]);
                                     }
    return 0;
    }
  评论这张
 
阅读(4)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018