misschuer

導(dǎo)航

<

2009年4月

>

日

一

二

三

四

五

六

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

公告

留言簿

隨筆分類(lèi)

文章分類(lèi)

acm (rss)
Java (rss)

隨筆檔案

文章檔案

2009年4月 (1)

閱讀排行榜

評(píng)論排行榜

常用鏈接

統(tǒng)計(jì)

隨筆 - 61
文章 - 1
評(píng)論 - 18
引用 - 0

積分與排名

積分 - 24987
排名 - 727

百事通

hao123
WPL
杭電
松松
星和

(轉(zhuǎn))最短路徑模版(Dijkstra)

#include <iostream>

#include <queue>

using namespace std;

typedef struct

{

long v;

long next;

long cost;

}Edge;

typedef struct

{

long v;

long cost;

}node;

bool operator <(const node &a,const node &b)

{

return a.cost>b.cost;

}

const long MAXN=10000;

priority_queue<node> q;

long m,n;//點(diǎn),邊

long p[MAXN];

Edge e[MAXN];

bool vist[MAXN];

void init()

{

memset(p,-1,sizeof(p));

memset(vist,0,sizeof(vist));

while (!q.empty())

{

q.pop();

}

long i;

long eid=0;

for (i=0;i<m;++i)

{

long from,to,cost;

scanf("%ld %ld %ld",&from,&to,&cost);

e[eid].next=p[from];

e[eid].v=to;

e[eid].cost=cost;

p[from]=eid++;

//以下為無(wú)向圖使用

swap(from,to);

e[eid].next=p[from];

e[eid].v=to;

e[eid].cost=cost;

p[from]=eid++;

}

void print(long cost)

{

//cost==-1 則無(wú)解

printf("%ld\n",cost);

}

void Dijkstra()

{

init();

long cost=0;

long Start,End;

scanf("%ld %ld",&Start,&End);

node t;

t.cost=0;

t.v=Start;

q.push(t);

while (!q.empty())

{

t=q.top();

q.pop();

if (t.v==End)

{

break;

}

if (vist[t.v])

{

continue;

}

vist[t.v]=true;

long j;

for (j=p[t.v];j!=-1;j=e[j].next)

{

if (!vist[e[j].v])

{

node temp;

temp.v=e[j].v;

temp.cost=e[j].cost+t.cost;

q.push(temp);

}

if (t.v==End)

{

cost=t.cost;

}

else

{

cost=-1;

}

print(cost);

}

int main()

{

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

{

Dijkstra();

}

return 0;

}

posted on 2010-01-11 20:44 此最相思閱讀(150) 評(píng)論(0) 編輯收藏引用

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

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