首页 > 代码库 > oj2894(贝尔曼福特模板）

oj2894(贝尔曼福特模板）

2024-07-09 22:37:48   222人阅读

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 10000001using namespace std;struct node{    int x,y,w;}edge[4000002];int dis[500002];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=0;i<=n;i++)        dis[i]=N;      dis[s]=0;    for(int i=1;i<=n-1;i++)    {        flag=0;        for(int j=0;j<t;j++)        {            if(dis[edge[j].x]+edge[j].w<dis[edge[j].y])            {                   flag=1;                  dis[edge[j].y]=dis[edge[j].x]+edge[j].w;            }        }        if(flag==0) break;    }    printf("%d\n",dis[e]);}int main(){    int xx,yy,zz;    while(scanf("%d%d",&n,&m)!=EOF)    {        t=0;        while(m--)        {            scanf("%d%d%d",&xx,&yy,&zz);            add(xx,yy,zz);            add(yy,xx,zz);        }        scanf("%d%d",&s,&e);        B();    }    return 0;} /**************************************    Problem id    : SDUT OJ 2894     User name    : zlh130205张明成     Result        : Accepted     Take Memory    : 49344K     Take Time    : 710MS     Submit Time    : 2014-06-27 13:32:27  **************************************/

 


联系
我们