DarkKris
2016-08-30 11:13
采纳率: 100%
浏览 1.2k
已采纳

C++ 两个程序比较 为什么我的SPFA慢一些?

本人是一个OIer,在做一道图论题时遇到了一个困难:为什么我和拿满分的人做法一样而我的程序却因为超时只拿了40分?

题目名称:香甜的黄油

特地前来此处请教一下各路大神:
下面是我的40分代码:

 #include <iostream>
#include <cstdio>
using namespace std;
const int maxp=805,maxm=1455;
int n,p,cc,numP;
int firstEdge[maxp],nextEdge[2*maxm],weight[2*maxm],endPoint[2*maxm];
int s[505],dist[maxp],ans;
int queue[100*maxp],head,tail;
bool used[maxp];
void add(int x,int y,int w)
{
    weight[++numP]=w;
    endPoint[numP]=y;
    nextEdge[numP]=firstEdge[x];
    firstEdge[x]=numP;
}
void enqueue(int a)
{
    queue[++tail]=a;
    used[a]=true;
}
int pop()
{
    head++;
    used[queue[head]]=false;
    return queue[head];
}
int main()
{
    cin>>n>>p>>cc;
    for(int k=1;k<=n;k++)
    {
        cin>>s[k];
    };
    int x,y,w;
    for(int i=1;i<=cc;i++)
    {
        cin>>x>>y>>w;
        add(x,y,w);
        add(y,x,w);
    };
    ans=0xffffff;

    for(int i=1;i<=p;i++)
    {
        head=0;tail=0;
        for(int j=1;j<=p;j++)
        {
            dist[j]=0xffffff;
            used[j]=false;
        };
        dist[i]=0;
        enqueue(i);
        int u,nowP;
        while(head<tail)
        {
            u=pop();
            nowP=firstEdge[u];
            while(nowP>0)
            {
                if(dist[endPoint[nowP]]>dist[u]+weight[nowP])
                    dist[endPoint[nowP]]=dist[u]+weight[nowP];
                if(!used[endPoint[nowP]])enqueue(endPoint[nowP]);
                nowP=nextEdge[nowP];
            };
        };
        int res=0;
        for(int j=1;j<=n;j++)
            res+=dist[s[j]];
        if(res<ans)ans=res;
    }
    cout<<ans;
    return 0;
}

这是满分代码(Pascal)

program butter;
var i,j,n,p,c,min,tot,t,x,y,z:longint;
    v,next,head,cost,dis,b:array[0..3000]of longint;
    team:array[0..10100]of longint;
    pd:array[0..3000]of boolean;
procedure add(x,y,z:longint);
begin
 inc(t);
  v[t]:=y;
  next[t]:=head[x];
  head[x]:=t;
  cost[t]:=z;
end;
procedure SPFA(x:longint);
var i,j,l,r,u,v1,e:longint;
begin
  for i:=1 to p do
    dis[i]:=maxlongint div 3;
     l:=0;
     r:=1;
     team[1]:=x;
     pd[x]:=true;
     dis[x]:=0;
      while l<>r do
        begin
          l:=l mod 1600+1;
          u:=team[l];
          pd[u]:=false;
          e:=head[u];
           while e<>0 do
             begin
               v1:=v[e];
                if dis[v1]>dis[u]+cost[e] then
                    begin
                     dis[v1]:=dis[u]+cost[e];
                       if pd[v1]=false then begin
                                              r:=r mod 1600+1;
                                              team[r]:=v1;
                                              pd[v1]:=true;
                                             end;
                    end;
                 e:=next[e];
             end;
        end;
end;
begin
readln(n,p,c);
min:=maxlongint;
 for i:=1 to n do
   readln(b[i]);
    for i:=1 to c do
      begin
       readln(x,y,z);
       add(x,y,z);
       add(y,x,z);
      end;
    for i:=1 to p do
      begin
       tot:=0;
       SPFA(i);
       for j:=1 to n do
         tot:=tot+dis[b[j]];
         if tot<min then min:=tot;
      end;
   writeln(min);
end. 
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • DarkKris 2016-09-03 13:01
    已采纳

    自己明白了,这是一道著名的卡SPFA算法的题目,用dijkstra+堆优化就可以过了

    点赞 打赏 评论
  • 夜幕下的ACM之路 2016-08-31 06:31

    你试试把cin,cout全部改为scanf和printf试试

    点赞 打赏 评论

相关推荐 更多相似问题