T9的空間

You will never walk alone!

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

69 隨筆 :: 0 文章 :: 28 評論 :: 0 Trackbacks

<

2008年9月

>

日

一

二

三

四

五

六

31

1

2

3

4

5

6

8

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

10

11

公告

如果筆記中有誤導路人的段落，請幫忙email給我，謝謝 shuoxie@gmail.com

隨筆分類

隨筆檔案

搜索

積分與排名

積分 - 49599
排名 - 465

最新評論

1.?re: ACM OJ Collection
評論內容較長,點擊標題查看
--professional resume writing service

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

只有注冊用戶登錄后才能發表評論。


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

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

T9的空間

公告

隨筆分類

隨筆檔案

相冊

收藏夾

我的鏈接

搜索

積分與排名

最新隨筆

最新評論