设为首页 加入收藏

TOP

HDU 1535 Invitation Cards （POJ 1511）
2015-07-24 05:49:46 来源: 作者: 【大 中 小】 浏览:4次
Tags：HDU 1535 Invitation Cards POJ 1511

两次SPFA。求 来 和 回 的最短路之和。

用Dijkstra+邻接矩阵确实好写+方便交换，但是这个有1000000个点，矩阵开不了。


d1[]为 1~N 的最短路。

将所有边的 邻点 交换。

d2[] 为 1~N 的最短路。


所有相加为 所要答案。

忧伤的是用SPFA “HDU 1535” AC了，但是POJ 一样的题 “POJ 1511” 就WA了。


然后强迫症犯了，不停的去测试。


题意中找到一句关键话 ：Prices are positive integers the sum of which is smaller than 1000000000

本来int 可以的。HDU 就是这样。

然后我就把POJ的求和 改成了 long long 。还是WA。

然后发现 我的INF 有问题，0xfffffff 不够。然后改成0x7fffffff int的最大值，AC了。

POJ 数据也真是?。完全不看题意的。


#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n,m; struct lx { int v,d; }; int dis[1000001]; bool vis[1000001]; int e[1000001]; vector
              
               g[1000001]; void swapg() { for(int i=1;i<=n;i++) e[i]=g[i].size(); for(int i=1;i<=n;i++) { int u,v,d; lx now; u=i; for(int j=0;j
               
                q; dis[1]=0,vis[1]=1; q.push(1); while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int j=e[u];j
                
                 dis[u]+d) { dis[v]=dis[u]+d; if(!vis[v]) { vis[v]=1; q.push(v); } } } } int ans=0; //long long for(int i=1;i<=n;i++) ans+=dis[i]; return ans; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int u,v,d; lx now; for(int i=1;i<=n;i++) g[i].clear(); while(m--) { scanf("%d%d%d",&u,&v,&d); now.d=d; now.v=v; g[u].push_back(now); } memset(e,0,sizeof(e)); int dis1=SPFA(n); //long long swapg(); int dis2=SPFA(n); //long long printf("%d\n",dis1+dis2); // lld% } }




【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：HDU 3605Escape（缩点+网络流之最.. 下一篇：Codeforces 442B Kolya and Tande..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: