随笔 - 32  文章 - 2  trackbacks - 0
<2008年11月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

常用链接

留言簿(3)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 8793
  • 排名 - 1247

最新评论

阅读排行榜

评论排行榜

预处理麻烦一些的floyd。
值得注意的是 floyd 循环的顺序千万不能搞错。
 1#include <iostream>
 2using namespace std;
 3const int OO(1000000);
 4int m,n,mem,mlist[31],dis[201][201],ans[201];
 5bool map[201][251][251];
 6bool con[251][201];
 7int 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)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理