算法nodehdu 2112 hdu today-白红宇

算法nodehdu 2112 hdu today

阅读量：5118 次

发布时间：2019-06-13

本文共 2180 字，大约阅读时间需要 7 分钟。

最近朋友几篇文章介绍了改算法node的文章. 关联文章的地址

被这个水题虐了一晚上，就是因为tot没有初始化，初始化为0的时候就是不超时的时候。这个标题其实还是单源点最短路，稍微有点眇乎小哉的难度，那就是这个标题都会的代号不再是简单的数字了，取而代之的是string的类型。其实很好办，你用map处理一下，这个标题立刻就被打回原形了。这个标题我还是用spfa算法停止的处理，因为这个算法真的挺好用的。直接就是模板题。擦，还被这个悲催的tot摆了一道。

上面看代码，不解释直接就是spfa的最基本用法。

每日一道理

正所谓“学海无涯”。我们正像一群群鱼儿在茫茫的知识之海中跳跃、嬉戏，在知识之海中出生、成长、生活。我们离不开这维持生活的“海水”，如果跳出这个“海洋”，到“陆地”上去生活，我们就会被无情的“太阳”晒死。

#include
    
     #include
     
      #include
      #include
       
        #include
        
         #include
         
          using namespace std;map
          
            A;int list[205];int dist[205];const int inf=10000000;struct node{ int start; int end; int len; int next;};node edge[20010];int vis[205];int tot,n,m,s,t,coun;void add(int a,int b,int c){ tot=tot+1; edge[tot].start=a; edge[tot].end=b; edge[tot].len=c; edge[tot].next=list[a]; list[a]=tot; tot=tot+1; edge[tot].start=b; edge[tot].end=a; edge[tot].len=c; edge[tot].next=list[b]; list[b]=tot;}void spfa(int s){ int i,now; queue
           
             q; for(i=1;i<=coun;i++) dist[i]=inf; dist[s]=0; vis[s]=1; q.push(s); while(!q.empty()) { now=q.front(); q.pop(); vis[now]=0; for(i=list[now];i!=-1;i=edge[i].next) { int temp=dist[now]+edge[i].len; if(dist[edge[i].end]>temp) { dist[edge[i].end]=temp; if(vis[edge[i].end]==0) { vis[edge[i].end]=1; q.push(edge[i].end); } } } }}int main(){ string str1,str2,beg,en; int i,chang; while(scanf("%d",&n)!=EOF&&n!=-1) { A.clear(); cin>>beg>>en; memset(list,-1,sizeof(list)); memset(vis,0,sizeof(vis)); A[beg]=1; A[en]=2; coun=3; tot=0; for(i=1;i<=n;i++) { cin>>str1>>str2>>chang; if(A.find(str1)==A.end()) { A[str1]=coun++; } if(A.find(str2)==A.end()) { A[str2]=coun++; } add(A[str1],A[str2],chang); } spfa(A[beg]); if(dist[A[en]]==inf) printf("-1\n"); else printf("%d\n",dist[A[en]]); } return 0;}

文章结束给大家分享下程序员的一些笑话语录：神灯新篇

一个程序员在海滩上发现了一盏神灯。他在灯上擦了几下，一个妖怪就从灯里跳出来说：“我是世界上法术最强的妖怪。我可以实现你的任何梦想，但现在，我只能满足你一个愿望。”程序员摊开了一幅中东地图说：“我想让中东得到永久的和平。”妖怪答道：“哦，我没办法。自打创世纪以来，那里的战火就没有停息过。这世上几乎没有我办不到的事，但这件事除外。”程序员于是说：“好吧，我是一个程序员，为许多用户编写过程序。你能让他们把需求表述得更清楚些，并且让我们的软件项目有那么一两次按进度按成本完成吗？”妖怪说：“唔，我们还是来看中东地图吧。”

--------------------------------- 原创文章 By

算法和node

---------------------------------

转载于:https://www.cnblogs.com/jiangu66/archive/2013/05/30/3109163.html

你可能感兴趣的文章