oj2894(贝尔曼福特模板）

时间：2024-10-24 12:37:02

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2894

就因为粗心，一中午没A,题目说是2000000条边无向图，我数组却开了2000000真是该死，我一看别人A的状态，内存都比我大一倍，瞬间知道自己手残了，明明是4000000啊，

但令我不解的是说SPFA是BE的改良版，但为什么7100ms,虐心，完全坑爹。

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define N 10000001

using namespace std;

struct node

{

    int x,y,w;

}edge[];

int dis[];

int n,m,s,e;

int t,flag;

void add(int x1,int y1,int w1)

{

    edge[t].x=x1;

    edge[t].y=y1;

    edge[t++].w=w1;

}

void B()

{

    for(int i=;i<=n;i++)

        dis[i]=N;

      dis[s]=;

    for(int i=;i<=n-;i++)

    {

        flag=;

        for(int j=;j<t;j++)

        {

            if(dis[edge[j].x]+edge[j].w<dis[edge[j].y])

            {

                   flag=;

                  dis[edge[j].y]=dis[edge[j].x]+edge[j].w;

            }

        }

        if(flag==) break;

    }

    printf("%d\n",dis[e]);

}

int main()

{

    int xx,yy,zz;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        t=;

        while(m--)

        {

            scanf("%d%d%d",&xx,&yy,&zz);

            add(xx,yy,zz);

            add(yy,xx,zz);

        }

        scanf("%d%d",&s,&e);

        B();

    }

    return ;

}

/**************************************

    Problem id    : SDUT OJ 2894

    User name    : zlh130205张明成

    Result        : Accepted

    Take Memory    : 49344K

    Take Time    : 710MS

    Submit Time    : 2014-06-27 13:32:27

**************************************/

相关文章