#include <iostream>
#include<stdio.h>

#define MAX 0xfffffff
#define MIN 0x-fffffff
#define NUM 3000
using namespace std;

__int64 V,E,border[NUM][NUM],midborder[NUM][NUM],tempborder[NUM][NUM],sum,sum2;
__int64 visit[NUM];

void copy()
{
    __int64 i,j;
    for(i=1;i<=V;i++)
    for(j=1;j<=V;j++)
    midborder[i][j]=border[i][j];
}

void SPFA1()
{
    __int64 queue[NUM],data[NUM];
    queue[1]=1;
    __int64 i,j;
    __int64* p1,*p2;
    p1=&queue[1];
    p2=p1+1;
sum=0;memset(visit,0,sizeof(visit));//初始化
    for(i=1;i<=V;i++)
        data[i]=MAX;
	data[1]=0;
    while(p1!=p2)
    {
        __int64 now=data[*p1];
		if(p1+1==&queue[NUM-1]) p1=&queue[1];
        for(i=1;i<=V;i++)
        {
            if(now+border[*p1][i]<data[i])
            {
                if(!visit[i])
                {
                    data[i]=now+border[*p1][i];
                    visit[i]=1;
                     if(p2==&queue[NUM-1])
                     {
                       p2=&queue[1];
                       *p2=i;
                     }
                     else *(p2++)=i;
                }
                else data[i]=now+border[*p1][i];
            }
        }
		visit[*p1]=0;
		p1++;
    }
    for(i=1;i<=V;i++)
		sum+=data[i];
}
void SPFA2()
{
    __int64 queue[NUM],data[NUM];
    queue[1]=1;
    __int64 i,j;
    __int64* p1,*p2;
    p1=&queue[1];
    p2=p1+1;
sum2=0;memset(visit,0,sizeof(visit));//初始化
    for(i=1;i<=V;i++)
        data[i]=MAX;
	data[1]=0;
    while(p1!=p2)
    {
        __int64 now=data[*p1];
		if(p1+1==&queue[NUM-1]) p1=&queue[1];
        for(i=1;i<=V;i++)
        {
            if(now+border[i][*p1]<data[i])
            {
                if(!visit[i])
                {
                    data[i]=now+border[i][*p1];
                    visit[i]=1;
                     if(p2==&queue[NUM-1])
                     {
                       p2=&queue[1];
                       *p2=i;
                     }
                     else *(p2++)=i;
                }
                else data[i]=now+border[i][*p1];
            }
        }
		visit[*p1]=0;
		p1++;
    }
    for(i=1;i<=V;i++)
		sum2+=data[i];
}

int main()
{
    __int64 cases;
    __int64 i,j,s,e,dis;
    scanf("%I64d",&cases);
    while(cases--)
    {
sum2=0;
        scanf("%I64d %I64d",&V,&E);
        for(i=1;i<=V;i++)
        for(j=1;j<=V;j++)
        {
            if(i==j) border[i][j]=0;
            else border[i][j]=MAX;
        }
        for(i=1;i<=E;i++)
        {
            scanf("%I64d %I64d %I64d",&s,&e,&dis);
            border[s][e]=dis;
        }
        copy();//保存
        SPFA1();
        SPFA2();
		printf("%I64d\n",sum+sum2);
    }
    return 0;
}

• Re:帮我看看SPFA。。。我3天了没过了。。。 (36) lenglengmajia 2009-04-19 11:57:52
• 据说栈实现SPFA比队列要快..不知大牛们怎么想? (2) lenglengmajia 2009-04-19 11:59:30