隨筆 - 87 文章 - 279 trackbacks - 0

2006年8月

日

一

二

三

四

五

六

潛心看書(shū)研究！

常用鏈接

留言簿(19)

隨筆分類(lèi)(81)

文章分類(lèi)(89)

相冊(cè)

ACM OJ

HOJ
POJ
TOJ
URAL
UVA
ZOJ

My friends

搜索

積分與排名

積分 - 216719
排名 - 117

閱讀排行榜

評(píng)論排行榜

Floyd-warshall(經(jīng)典DP, 能用于有向圖)

聞?wù)f還能用在負(fù)權(quán),和有環(huán)圖...繼續(xù)研究

const ? int ?MAXN? = ? 101 ;

const ? int ?INF? = ? 1000000 ;

int ?g[MAXN][MAXN];

int ?d[MAXN][MAXN];

int ?floyd( int ?n)

{

???? int ??i,?j,?k;

???? for ?(i = 1 ;?i <= n;?i ++ )

???????? for ?(j = 1 ;?j <= n;?j ++ )

????????????d[i][j]? = ?g[i][j];

???? for ?(k = 1 ;?k <= n;?k ++ )

???? {

???????? for ?(i = 1 ;?i <= n;?i ++ )

???????????? for ?(j = 1 ;?j <= n;?j ++ )

???????????? {

???????????????? if ?(d[i][k]? < ?INF? && ?d[k][j]? < ?INF

???????????????? && ?d[i][k]? + ?d[k][j]? < ?d[i][j])

????????????????????d[i][j]? = ?d[i][k]? + ?d[k][j];

????????????}

????}

???? return ? 0 ;

}

posted on 2006-08-29 15:27 豪閱讀(1025) 評(píng)論(1) 編輯收藏引用所屬分類(lèi): 算法&ACM

FeedBack:

# re: Floyd-warshall(經(jīng)典DP, 能用于有向圖) 2006-09-01 23:08 踏雪赤兔

不能有負(fù)環(huán) 回復(fù) 更多評(píng)論

刷新評(píng)論列表

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

相關(guān)文章: 用stl打spfa短了1k代碼，慢了200ms 三次樣條插值龍貝格積分2457jlu 三分法求函數(shù)極值buaa1024 為了大作業(yè)報(bào)告好寫(xiě)點(diǎn)，重寫(xiě)了RBTree 擴(kuò)展的歐拉函數(shù) pku1091 連分?jǐn)?shù)學(xué)習(xí)筆記中國(guó)剩余定理(同余方程組)小結(jié) 解模線(xiàn)性方程小結(jié) 好久沒(méi)寫(xiě)了.

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