SDUT 2894-C（最短路spfa） - c++编程基础

TOP

SDUT 2894-C（最短路spfa）

2015-07-20 17:49:03 来源: 作者: 【大中小】浏览:7次

Tags：SDUT 2894-C 短路 spfa

C

Time Limit: 7000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

给出一个带权无向图，包含n个点，m条边。求出s，e的最短路。保证最短路存在。

输入

多组输入。对于每组数据。第一行输入n，m(1<= n && n<=5*10^5,1 <= m && m <= 2*10^6)。
接下来m行，每行三个整数，u,v,w,表示u，v之间有一条权值为w(w >= 0)的边。
最后输入s，e。

输出

对于每组数据输出一个整数代表答案。

示例输入

3 1
1 2 3
1 2

示例输出

这道题绝了。。点 边都太多，要么spfa过，要么bfs+优先队列爆搜（好像更快一些） 其他的方法都过不去，而其对内存卡的特别紧，vector过不去，照着标程敲的bfs挂了。。到现在不知道错在哪，怒换spfa，然后就过了

#include 
   
    
#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                using namespace std; const int maxn=500010; const int INF=1<<29; struct node{ int p,w,next; }; node eg[4000010]; bool vis[maxn]; int n,e,head[500010],dis[500010]; void adj_clear() { memset(head,-1,sizeof(head)); e=0; } void addnode(int u,int v,int c) { eg[e].p=v; eg[e].w=c; eg[e].next=head[u]; head[u]=e++; } void spfa(int src) { queue 
               
                 Q;int i; for(i=0;i<=n;i++){dis[i]=INF;vis[i]=0;} dis[src]=0; Q.push(src); while(!Q.empty()){ int u=Q.front();Q.pop(); vis[u]=0; for(i=head[u];i!=-1;i=eg[i].next) { int v=eg[i].p; int w=eg[i].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; if(!vis[v]) { vis[v]=1; Q.push(v); } } } } } int main() { int u,v,m,w; while(scanf("%d%d",&n,&m)!=EOF){ adj_clear(); while(m--){ scanf("%d%d%d",&u,&v,&w); addnode(u,v,w); addnode(v,u,w); } int s,en; scanf("%d%d",&s,&en); spfa(s); printf("%d\n",dis[en]); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：zoj 3666 Alice and Bob ， SG函数	下一篇：从观察者模式的实现，看c/c++的语..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: