Standing on Shoulders of Giants
God Show me the way
C++博客
首页
新随笔
联系
聚合
管理
随笔 - 32 文章 - 2 trackbacks - 0
<
2008年4月
>
日
一
二
三
四
五
六
30
31
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
1
2
3
4
5
6
7
8
9
10
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(3)
给我留言
查看公开留言
查看私人留言
随笔档案
2008年11月 (26)
2008年6月 (1)
2008年4月 (5)
文章档案
2008年4月 (1)
搜索
积分与排名
积分 - 8805
排名 - 1247
最新评论
1. re: URAL 1024 Permutations
@zjhuijsj@163.com
讨论里面有
--Joseph
2. re: URAL 1024 Permutations
测试数据是怎么得到得
--zjhuijsj@163.com
阅读排行榜
1. pku题目分类(1097)
2. URAL 1090. In the army now(925)
3. URAL 1036 Lucky tickets(426)
4. 关于floyd求多源最短路循环顺序(396)
5. URAL 1095. Nikifor 3(346)
评论排行榜
1. URAL 1024 Permutations(2)
2. URAL 1029 Ministry(0)
3. URAL 1030 Titanic(0)
4. URAL 1031 Railway tickets(0)
5. URAL 1036 Lucky tickets(0)
pku 1161
预处理麻烦一些的floyd。
值得注意的是 floyd 循环的顺序千万不能搞错。
1
#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
12
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
16
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
40
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
44
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
阅读(183)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
博问
Chat2DB
管理