随笔 - 87 文章 - 279 trackbacks - 0

2006年8月

日

一

二

三

四

五

六

潜心看书研究！

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

积分与排名

积分 - 211944
排名 - 116

阅读排行榜

评论排行榜

Floyd-warshall(经典DP, 能用于有向图)

闻说还能用在负权,和有环图...继续研究

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 豪阅读(1008) 评论(1) 编辑收藏引用所属分类: 算法&ACM

FeedBack:

# re: Floyd-warshall(经典DP, 能用于有向图) 2006-09-01 23:08 踏雪赤兔

不能有负环回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。


相关文章: 用stl打spfa短了1k代码，慢了200ms 三次样条插值龙贝格积分2457jlu 三分法求函数极值buaa1024 为了大作业报告好写点，重写了RBTree 扩展的欧拉函数 pku1091 连分数学习笔记中国剩余定理(同余方程组)小结解模线性方程小结好久没写了.

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理