青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
lzm
who dare win.
posts - 14, comments - 29, trackbacks - 0, articles - 0
導航
C++博客
首頁
新隨筆
聯系
聚合
管理
<
2009年3月
>
日
一
二
三
四
五
六
22
23
24
25
26
27
28
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
常用鏈接
我的隨筆
我的評論
我參與的隨筆
留言簿
(2)
給我留言
查看公開留言
查看私人留言
隨筆分類
(13)
Algorithm(10)
OJ(3)
隨筆檔案
(14)
2009年4月 (11)
2009年3月 (2)
2008年10月 (1)
收藏夾
(4)
POJ
SL(4)
ZOJ
最新隨筆
1.?poj 1094 Sorting It All Out
2.?Floyd_Warshall算法
3.?Kruskal算法
4.?Prim算法
5.?Critical Path 關鍵路徑
6.?Bellman_Ford算法 SPFA算法
7.?Dijkstra算法
8.?USP 無權最短路徑算法
9.?Topsort 拓撲排序
10.?(正則表達式)是否匹配(字符串)
11.?Quicksort 快速排序
12.?poj 1024 Tester Program
13.?poj 1022 Packing Unit 4D Cubes
14.?加減乘除24
搜索
積分與排名
積分 - 39310
排名 - 546
最新評論
1.?re: Dijkstra算法
請問一下,這個路徑可以輸出成功嗎?為什么我的差不多可輸不出來呢?
prev[w] = v; 只加著一句就夠了嗎?
--毛
2.?re: (正則表達式)是否匹配(字符串)[未登錄]
呃……請問為什么我輸入A*G.C和AGTGTC,結果是dismatch呢?
--xyz
3.?re: Kruskal算法
這個程序是不是有個bug:
如果節點數量為1,邊數量為0
則應該是有生成樹的,但是kruskal函數返回結果為false吧
個人意見
--mwxjm
4.?re: 加減乘除24
想問下~為什么tb1函數要swap交換后在執行后有swap
--65666
5.?re: poj 1024 Tester Program[未登錄]
灰常感謝LZ,看了你的第5條那個,讓debug了3個小時的我一下就過了;
因為我的初始化原來是-1,所以釀成杯具啊。。
這bug。。汗。
--joy
閱讀排行榜
1.?Dijkstra算法(6228)
2.?Kruskal算法(4593)
3.?Prim算法(4373)
4.?(正則表達式)是否匹配(字符串)(3970)
5.?加減乘除24(2439)
評論排行榜
1.?加減乘除24(7)
2.?poj 1094 Sorting It All Out(5)
3.?Quicksort 快速排序(4)
4.?(正則表達式)是否匹配(字符串)(3)
5.?Dijkstra算法(3)
USP 無權最短路徑算法
Posted on 2009-04-09 10:44
lzmagic
閱讀(2239)
評論(0)
編輯
收藏
引用
所屬分類:
Algorithm
/**/
/*
*
* USP 無權最短路徑算法(Unweighted Shortest Path Algorithm)
* 輸入:(1)圖g; // 有向圖或者無向圖
* (2)源點s。
* 輸出:(1)源點s到各點的無權最短路徑長dist(路徑的邊數最小);
* (2)源點s到各點的無權最短路徑prev。
* 結構: 圖g用鄰接表表示,最短路徑長dist用數組表示。
* 算法:廣度優先搜索(BFS)
* 復雜度:O(|E|+|V|)~O(|E|)
*/
#include
<
iostream
>
#include
<
vector
>
#include
<
list
>
#include
<
queue
>
#include
<
iterator
>
#include
<
algorithm
>
#include
<
numeric
>
#include
<
functional
>
#include
<
climits
>
using
namespace
std;
int
n;
//
n : 頂點個數
vector
<
list
<
int
>
>
g;
//
g : 圖(graph)(用鄰接表(adjacent list)表示)
int
s;
//
s : 源點(source)
vector
<
int
>
dist;
//
dist : 源點s到各點之間的距離
vector
<
int
>
prev;
//
prev : 各點最短路徑的前一頂點號
void
USP()
//
廣度優先搜索(BFS)
{
queue
<
int
>
que;
dist.assign(n, INT_MAX);
//
初始化dist,
prev.resize(n);
//
初始化prev。
dist[s]
=
0
; que.push(s);
//
s到自身距離為0,s入隊。
while
(
!
que.empty())
{
int
v
=
que.front(); que.pop();
//
v出隊,
for
(list
<
int
>
::iterator it
=
g[v].begin(); it
!=
g[v].end();
++
it)
//
遍歷v相鄰點*it,
if
(dist[
*
it]
==
INT_MAX)
//
如果*it未訪問,
{
dist[
*
it]
=
dist[v]
+
1
; prev[
*
it]
=
v;
//
調整點*it,
que.push(
*
it);
//
*it入隊。
}
}
}
void
Print_SP(
int
v)
{
if
(v
!=
s) Print_SP(prev[v]);
cout
<<
v
<<
"
"
;
}
int
main()
{
n
=
7
;
g.assign(n, list
<
int
>
());
g[
0
].push_back(
1
); g[
0
].push_back(
3
);
g[
1
].push_back(
3
); g[
1
].push_back(
4
);
g[
2
].push_back(
0
); g[
2
].push_back(
5
);
g[
3
].push_back(
2
); g[
3
].push_back(
4
); g[
3
].push_back(
5
); g[
3
].push_back(
6
);
g[
4
].push_back(
6
);
g[
6
].push_back(
5
);
s
=
2
;
USP();
copy(dist.begin(), dist.end(), ostream_iterator
<
int
>
(cout,
"
"
)); cout
<<
endl;
for
(
int
i
=
0
; i
<
n;
++
i)
if
(dist[i]
!=
INT_MAX)
{
cout
<<
s
<<
"
->
"
<<
i
<<
"
:
"
;
Print_SP(i);
cout
<<
endl;
}
system(
"
pause
"
);
return
0
;
}
只有注冊用戶
登錄
后才能發表評論。
相關文章:
Floyd_Warshall算法
Kruskal算法
Prim算法
Critical Path 關鍵路徑
Bellman_Ford算法 SPFA算法
Dijkstra算法
USP 無權最短路徑算法
Topsort 拓撲排序
(正則表達式)是否匹配(字符串)
Quicksort 快速排序
網站導航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
Powered by:
C++博客
Copyright © lzmagic
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
欧美区日韩区
|
亚洲一区二区三区精品在线
|
欧美国产专区
|
亚洲欧美激情四射在线日
|
欧美乱人伦中文字幕在线
|
在线观看日产精品
|
欧美在线视频一区二区三区
|
在线亚洲电影
|
欧美性色综合
|
亚洲一区二区少妇
|
亚洲乱码精品一二三四区日韩在线
|
在线一区免费观看
|
免费欧美视频
|
久久精品一区蜜桃臀影院
|
国产精品一区二区久久精品
|
亚洲午夜视频
|
亚洲一品av免费观看
|
国产精品免费看片
|
欧美一级淫片aaaaaaa视频
|
亚洲免费影视
|
国产亚洲在线观看
|
久久这里只精品最新地址
|
久久偷看各类wc女厕嘘嘘偷窃
|
在线精品国产成人综合
|
欧美成人精精品一区二区频
|
欧美福利视频
|
亚洲一区免费看
|
午夜欧美视频
|
在线成人av网站
|
91久久精品国产91性色tv
|
新片速递亚洲合集欧美合集
|
黄色综合网站
|
亚洲人成在线观看一区二区
|
欧美午夜性色大片在线观看
|
久久精品成人一区二区三区
|
久久夜色精品国产亚洲aⅴ
|
日韩视频一区
|
亚洲欧美日韩国产中文
|
影音先锋日韩有码
|
亚洲精品一区二区三区四区高清
|
男人插女人欧美
|
久久久久久电影
|
亚洲欧洲日本mm
|
中国av一区
|
一区在线影院
|
日韩视频一区
|
国内视频精品
|
日韩午夜激情av
|
国产午夜精品全部视频在线播放
|
亚洲精品国产欧美
|
国产女人18毛片水18精品
|
欧美 日韩 国产在线
|
欧美日韩免费观看一区
|
亚洲一二三区视频在线观看
|
亚洲一本大道在线
|
亚洲激精日韩激精欧美精品
|
亚洲美女视频网
|
国产精品视频免费在线观看
|
亚洲第一搞黄网站
|
欧美日韩在线电影
|
欧美综合国产
|
国产精品h在线观看
|
欧美成在线观看
|
欧美午夜精品久久久久免费视
|
亚洲精品一区二区三区樱花
|
欧美一区国产一区
|
欧美一区二区三区日韩
|
亚洲精品资源
|
亚洲免费在线观看视频
|
亚洲精品在线二区
|
午夜性色一区二区三区免费视频
|
国产一区二区三区日韩
|
99re热这里只有精品视频
|
亚洲成人在线视频播放
|
亚洲午夜性刺激影院
|
日韩一级二级三级
|
久久久久9999亚洲精品
|
欧美一区亚洲一区
|
欧美日韩日本视频
|
亚洲国产一区二区a毛片
|
国产亚洲成av人在线观看导航
|
亚洲国产裸拍裸体视频在线观看乱了中文
|
久久久久国内
|
国产精品视频免费在线观看
|
亚洲精品偷拍
|
久久精品视频网
|
美女精品自拍一二三四
|
久久久久久高潮国产精品视
|
欧美天天综合网
|
亚洲国产一区视频
|
久久综合久久美利坚合众国
|
欧美在线看片
|
国产精品久久久久91
|
亚洲欧洲中文日韩久久av乱码
|
一区二区三区自拍
|
99精品欧美一区二区三区
|
亚洲国产日韩欧美
|
欧美影院成人
|
蜜臀91精品一区二区三区
|
国产视频综合在线
|
亚洲欧美日韩一区
|
欧美一区二区三区在线视频
|
欧美亚洲在线
|
中文在线资源观看视频网站免费不卡
|
午夜精品免费视频
|
国产精品va在线播放我和闺蜜
|
亚洲剧情一区二区
|
亚洲免费大片
|
欧美激情第8页
|
亚洲人成人99网站
|
日韩天堂在线观看
|
欧美电影免费观看网站
|
欧美成人r级一区二区三区
|
亚洲一区二区免费视频
|
欧美三级日本三级少妇99
|
亚洲美女精品成人在线视频
|
一区二区三区成人
|
欧美一区二区精品在线
|
久久福利毛片
|
精品动漫3d一区二区三区免费
|
在线日韩av片
|
美女在线一区二区
|
91久久久亚洲精品
|
免费观看成人www动漫视频
|
亚洲一区中文
|
欧美日韩影院
|
亚洲永久在线
|
久久午夜国产精品
|
99在线热播精品免费
|
好看的日韩av电影
|
久久久久久黄
|
亚洲看片一区
|
欧美成人中文字幕在线
|
久久精品国产精品亚洲
|
欧美bbbxxxxx
|
亚洲伊人观看
|
精品动漫3d一区二区三区
|
欧美日韩国产欧
|
欧美中文字幕第一页
|
99国产精品久久久久久久久久
|
久久国产福利
|
99精品欧美
|
国内外成人在线视频
|
欧美电影免费观看高清完整版
|
亚洲图片激情小说
|
亚洲国产欧美一区二区三区丁香婷
|
欧美精品一线
|
香蕉尹人综合在线观看
|
国产精品毛片在线
|
最近中文字幕日韩精品
|
久久精品成人一区二区三区
|
久久综合给合久久狠狠狠97色69
|
亚洲国产精品www
|
性欧美暴力猛交69hd
|
亚洲国产精品一区二区三区
|
国产精品成人在线观看
|
国产精品热久久久久夜色精品三区
|
亚洲精品少妇网址
|
久久综合电影
|
欧美一级黄色网
|
亚洲免费观看
|
狠狠爱成人网
|
国产日韩欧美三区
|
欧美激情综合亚洲一二区
|
香蕉久久一区二区不卡无毒影院
|
亚洲三级影片
|
欧美激情视频在线播放
|
久久精品夜夜夜夜久久
|
亚洲综合欧美日韩
|
亚洲啪啪91
|
国产在线成人
|
国产欧美一区二区三区在线看蜜臀
|
欧美大片在线看免费观看
|
亚洲精品资源
|
亚洲欧洲日本一区二区三区
|
久久久久久久久一区二区
|
亚洲无限乱码一二三四麻
|
亚洲人成网站在线观看播放
|
黑丝一区二区三区
|
亚洲高清一区二
|
伊人激情综合
|
红桃视频欧美
|
1024精品一区二区三区
|
好吊妞**欧美
|
亚洲第一页自拍
|
日韩一区二区精品
|
激情综合在线
|
一区二区三区在线观看视频
|
亚洲电影在线播放
|
伊人久久大香线蕉综合热线
|
国产手机视频一区二区
|
国产视频在线观看一区
|
亚洲激情啪啪
|
欧美国产日产韩国视频
|
午夜在线观看欧美
|
亚洲尤物视频在线
|
亚洲欧美不卡
|
亚洲一区二区三区精品视频
|
欧美亚洲视频
|
久久久女女女女999久久
|