国产精品视频精品视频,亚洲电影免费在线观看,国产一区二区三区高清

(轉(zhuǎn))SPFA算法模版+鄰接表

#include <iostream>

#include <queue>

using namespace std;

const long MAXN=10000;

const long lmax=0x7FFFFFFF;

typedef struct

{

long v;

long next;

long cost;

}Edge;

Edge e[MAXN];

long p[MAXN];

long Dis[MAXN];

bool vist[MAXN];

queue<long> q;

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

void init()

{

long i;

long eid=0;

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

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

fill(Dis,Dis+MAXN,lmax);

while (!q.empty())

{

q.pop();

}

for (i=0;i<n;++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++;

//以下適用于無向圖

swap(from,to);

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

e[eid].v=to;

e[eid].cost=cost;

p[from]=eid++;

}

void print(long End)

{

//若為lmax 則不可達(dá)

printf("%ld\n",Dis[End]);

}

void SPF()

{

init();

long Start,End;

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

Dis[Start]=0;

vist[Start]=true;

q.push(Start);

while (!q.empty())

{

long t=q.front();

q.pop();

vist[t]=false;

long j;

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

{

long w=e[j].cost;

if (w+Dis[t]<Dis[e[j].v])

{

Dis[e[j].v]=w+Dis[t];

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

{

vist[e[j].v]=true;

q.push(e[j].v);

}

print(End);

}

int main()

{

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

{

SPF();

}

return 0;

}

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

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



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

misschuer

導(dǎo)航

公告

留言簿

隨筆分類

文章分類

隨筆檔案

文章檔案

閱讀排行榜

評(píng)論排行榜

常用鏈接

統(tǒng)計(jì)

積分與排名

百事通

最新評(píng)論

(轉(zhuǎn))SPFA算法模版+鄰接表