T9的空间

You will never walk alone!
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks
POJ 1511(spfa)
http://acm.pku.cn/JudgeOnline/problem?id=1511
两个图，spfa正向求一次，反向求一次
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int Nmax=1000001;
const int oo=0x7fffffff;

typedef struct node
{
    int next;
    int e;
    int w;
}node;

int dis[Nmax];
node g[Nmax];
node reg[Nmax];
int p[Nmax];
int rep[Nmax];

queue<int>q;
bool usd[Nmax];
int i,j,k;

int Min[Nmax];

void SPFA(node g[],int p[])
{
    while(!q.empty ()) q.pop();
    memset(usd,false,sizeof(usd));
    memset(dis,0x7f,sizeof(dis));
    q.push(1); dis[1]=0;
    usd[1]=true;
    while(!q.empty())
    {
        int tmp=q.front ();
        q.pop();
        for(j=p[tmp];j!=-1;j=g[j].next)
        {
            if(dis[tmp]<oo&&dis[tmp]+g[j].w<dis[g[j].e])
            {
                dis[g[j].e]=dis[tmp]+g[j].w;
                if(!usd[g[j].e]) 
                {
                    q.push(g[j].e);
                    usd[g[j].e]=true;
                }
            }
        }
    }
}


int main()
{
    int P,Q;
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&P,&Q);
        int from,to,cost;
        int cnt=0,cnt1=0;
        memset(p,-1,sizeof(p));
        memset(rep,-1,sizeof(rep));
        for(i=1;i<=Q;i++)
        {
            scanf("%d%d%d",&from,&to,&cost);
            g[cnt].next=p[from];
            g[cnt].e=to;
            g[cnt].w=cost;
            p[from]=cnt++;

            reg[cnt1].next=rep[to];
            reg[cnt1].e=from;
            reg[cnt1].w=cost;
            rep[to]=cnt1++;
        }
        SPFA(g,p);
        memcpy(Min,dis,sizeof(dis));
        SPFA(reg,rep);
        for(i=1;i<=P;i++)
             Min[i]+=dis[i];
        __int64 re=0;
        for(i=2;i<=P;i++)
             re+=Min[i];
        printf("%I64d\n",re);
    }
    return 0;
}

posted on 2008-09-12 11:17 Torres 阅读(499) 评论(0)  编辑 收藏 引用 所属分类: Graph

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理