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 閱讀(514) 評論(0) 編輯收藏引用所屬分類: Graph

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: POJ 2502 Floyd POJ 1511(spfa) SPFA (Shortest Path Faster Algorithm) POJ3159 POJ2387（Dijkstra） HUST 1163

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

T9的空間

公告

隨筆分類

隨筆檔案

相冊

收藏夾

我的鏈接

搜索

積分與排名

最新隨筆

最新評論