pku 1161 - Standing on Shoulders of Giants

pku 1161

预处理麻烦一些的floyd。
值得注意的是 floyd 循环的顺序千万不能搞错。

#include <iostream>
2

using namespace std;
3

const int OO(1000000);
4

int m,n,mem,mlist[31],dis[201][201],ans[201];
5

bool map[201][251][251];
6

bool con[251][201];
7

int main(){
8

cin>>m;
9

cin>>n;
10

cin>>mem;
11

for (int i=1;i<=m;++i)
13

for (int j=1;j<=m;++j) dis[i][j]=OO;
14

for (int i=1;i<=m;++i) dis[i][i]=0;
15

for (int i=1;i<=mem;++i) scanf("%d",&mlist[i]);
17

for (int i=1;i<=m;++i) {
18

int num,list[251];
19

scanf("%d",&num);
20

for (int j=1;j<=num;++j) {
21

scanf("%d",&list[j]);
22

con[list[j]][i]=true;
23

if (j>1) {
24

map[i][list[j]][list[j-1]]=true;
25

map[i][list[j-1]][list[j]]=true;
26

for (int k=1;k<i;++k) if (map[k][list[j]][list[j-1]]) {
27

dis[i][k]=1;
28

dis[k][i]=1;
29

}
30

}
31

}
32

map[i][list[1]][list[num]]=true;
33

map[i][list[num]][list[1]]=true;
34

for (int j=1;j<i;++j) if (map[j][list[1]][list[num]]) {
35

dis[i][j]=1;
36

dis[j][i]=1;
37

}
38

}
39

for (int k=1;k<=m;++k)
41

for (int i=1;i<=m;++i)
42

for (int j=1;j<=m;++j) if (dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j];
43

for (int i=1;i<=mem;++i)
45

for (int j=1;j<=m;++j) {
46

int min=OO;
47

for (int k=1;k<=m;++k) if ((con[mlist[i]][k])&&(dis[k][j]<min)) min=dis[k][j];
48

ans[j]+=min;
49

}
50

int min=OO;
51

for (int i=1;i<=m;++i) if (ans[i]<min) min=ans[i];
52

cout<<min<<endl;
53

}
54

posted on 2008-04-11 21:33 Joseph 阅读(177) 评论(0) 编辑收藏引用

常用链接

留言簿(3)

随笔档案

文章档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

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




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