poj 1511 Invitation Cards(SPFA)

解题思路

题意：

给出n个顶点m条边的有向图，算出从第1点到其他各个顶点的最短路径的和，再算出从其他各个顶点到第一个顶点的最短路径的和，求出两个和的和。

 

思路：

       单源最短路径，而且又是非负权边，马上就想到用dijkstra，建两个邻接表，一个是跟题目给出的一样的，另一个是把第一个图中的边反向，权不变，然后分别用一次dijkstra，结果相加就ok了。

昨天的校热身赛这样做A了，可是北大上一提交确是TEL，因为它数据规模太大了，让我不得不去学新的算法——SPFA，果然很强大，只是6s多的时间搞得我很纠结。不得不想办法去优化，感谢1015的指教， 原来我的程序跑那么慢是因为，每次建邻接表的时候都要给指针申请空间，最多会有1000000*2个。然后他就提出在初始化时就给那么多指针分配好空间，果然效果不错，一下子飙到1700ms+。

Ps：这个题写了好几个版本，邻接阵+dij，邻接表+dij，邻接表+spfa(queue)，边数组+spfa(stack)， 邻接表+spfa(stack)，邻接表+边数组+spfa(stack) (最终版)，写得我好郁闷!

 

源程序

 

/*邻接表+spfa+stack*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define N 1000005
#define inf 1000000000

int n;
 struct edge
{
    struct edge *next;
    int vid;
    int info;
 }g[N],g1[N];

 typedef struct edge *Pedge;

 Pedge p[N],q[N];    // 搞指针数组，初始化时就给那么多指针分配空间

 int dis[N];
 int stack[N],mark[N];

__int64 spfa(edge gg[],Pedge y[], int n)
{
    __int64 sum;   //不用__int64会错
    int top;
    int i, k;
    struct edge *x;

    for(i=1; i<=n; i++)
        dis[i] = inf;

    memset(mark,0,sizeof(mark));
    top = 1;
    dis[1] = 0;
    mark[1] = 1;
    stack[top] = 1;
    while(top>0)
    {
    
        k = stack[top];
        top--;
        mark[k] = 0;
        for(x=y[k]; x!=NULL; x=x->next)
        {
            if(dis[k]!=inf&&dis[x->vid] > dis[k] + x->info)
            {
                dis[x->vid] = dis[k] + x->info;
                if(!mark[x->vid])
                {
                    top++;
                    mark[x->vid] = 1;
                    stack[top] = x->vid;
                }
            }
        }        
    }
    sum = 0;
    for(i=2; i<=n; i++)
    {
        sum += dis[i];
    }
    return sum;

}
int main()
{
    int i, j;
    int t, m, a, b, c;
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for(i=1; i<=n; i++)
        {
            p[i] = NULL;
            q[i] = NULL;
        }

        for(i=1; i<=m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            
            g[i].vid = b;
            g[i].info = c;
            g[i].next = p[a];
            p[a] = &g[i];

            g1[i].vid = a;
            g1[i].info = c;
            g1[i].next = q[b];
            q[b] = &g1[i];
        }
        printf("%I64d\n", spfa(g,q,n)+spfa(g1,p,n));
    }
    return 0;
}