pku 1847

2009年7月24日

题目链接：PKU 1847 Tram

分类：最短路

题目分析与算法原型
         将需要搬动的开关的节点的权值设为1，不需要搬动的开关设为0，不可达的设为一个充分大的数，这样一来，此题就转换为最短路径问题了，3种方法（Dijkastra,Floyd以及Bellman-Ford）都可以解决

Code1: （Floyd）

 1#include<stdio.h>
 2#define Len 105
 3#define max 99999999
 4
 5int a[Len][Len],i,j,k,n,A,B,t;
 6
 7void init()
 8{
 9    for(i=1;i<=n;i++)
10        for(j=1;j<=n;j++)
11        {
12            if(i==j)a[i][j]=0;
13            else a[i][j]=max;
14        }
15}
16int main()
17{
18    scanf("%d%d%d",&n,&A,&B);
19    init();
20    for(i=1;i<=n;i++)
21    {
22        scanf("%d",&k);
23        for(j=1;j<=k;j++)
24        {
25            scanf("%d",&t);
26            if(j==1)a[i][t]=0;
27            else a[i][t]=1;
28        }
29    }
30    for(k=1;k<=n;k++)
31        for(i=1;i<=n;i++)
32            for(j=1;j<=n;j++)
33                if(a[i][k]+a[k][j]<a[i][j])a[i][j]=a[i][k]+a[k][j];
34    
35    if(a[A][B]==max)printf("-1\n");
36    else printf("%d\n",a[A][B]);
37    return 0;
38}
39
40
 Code2:    (Dijkastra)
 
 1#include<stdio.h>
 2#include<string.h>
 3#define Len 105
 4#define max 99999999
 5int a[Len][Len],i,j,k,n,A,B,t,flag[Len],dis[Len],min,u;
 6void init()
 7{
 8    for(i=1;i<=n;i++)
 9        for(j=1;j<=n;j++)
10        {
11            if(i==j)a[i][j]=0;
12            else a[i][j]=max;
13        }
14}
15void Dij()
16{
17    for(i=1;i<=n;i++)dis[i]=a[A][i];
18    flag[A]=1;
19    for(i=1;i<n;i++)
20    {
21        min=max;
22        for(j=1;j<=n;j++)
23            if(flag[j]==0&&dis[j]<min)
24            {
25                u=j;
26                min=dis[j];
27            }
28            if(min==max)return;
29
30            flag[u]=1;
31            for(j=1;j<=n;j++)
32                if(flag[j]==0&&a[u][j]<max&&dis[u]+a[u][j]<dis[j])
33                    dis[j]=dis[u]+a[u][j];
34    }
35}
36int main()
37{
38    scanf("%d%d%d",&n,&A,&B);
39    init();
40    memset(flag,0,sizeof(flag));
41    for(i=1;i<=n;i++)
42    {
43        scanf("%d",&k);
44        for(j=1;j<=k;j++)
45        {
46            scanf("%d",&t);
47            if(j==1)a[i][t]=0;
48            else a[i][t]=1;
49        }
50    }
51    Dij();
52    if(dis[B]==max)printf("-1\n");
53    else printf("%d\n",dis[B]);
54    return 0;
55}
56
57
Code3:(Bellman-Ford) 

 1#include<stdio.h>
 2#define Len 105
 3#define max 99999999
 4
 5int a[Len][Len],k,n,A,B,t,dis[Len];
 6
 7void init()
 8{
 9    int i,j;
10    for(i=1;i<=n;i++)
11        for(j=1;j<=n;j++)
12        {
13            if(i==j)a[i][j]=0;
14            else a[i][j]=max;
15        }
16}
17
18void bellman_ford()
19{
20    int queue[Len*100]={0},pos=0,fp=0,i;
21    queue[pos++]=A;
22    queue[pos++]=n+1;
23    for(i=1;i<=n;i++)dis[i]=max;
24    dis[A]=0;
25    int N=1;
26    while(queue[fp])
27    {
28        int u;
29        while((u=queue[fp++])==n+1)
30        {
31            if(N++>n+1)return ;
32            queue[pos++]=n+1;
33        }
34        for(i=1;i<=n;i++)
35        {
36            if(i!=u&&a[u][i] < max)
37            {
38                if(dis[i]>dis[u]+a[u][i])
39                {
40                    dis[i]=dis[u]+a[u][i];
41                    queue[pos++]=i;
42                }
43            }
44        }
45    }
46}
47
48int main()
49{
50    scanf("%d%d%d",&n,&A,&B);
51    init();
52    int i,j;
53    for(i=1;i<=n;i++)
54    {
55        scanf("%d",&k);
56        for(j=1;j<=k;j++)
57        {
58            scanf("%d",&t);
59            if(j==1)a[i][t]=0;
60            else a[i][t]=1;
61        }
62    }
63    bellman_ford();
64    if(dis[B]==max)printf("-1\n");
65    else printf("%d\n",dis[B]);
66    return 0;
67}
68
Code4:(Bellman-Ford)

 1#include<stdio.h>
 2#define Len 105
 3#define max 99999999
 4
 5int a[Len][Len],i,j,k,n,A,B,t,dis[Len];
 6
 7void init()
 8{
 9    for(i=1;i<=n;i++)
10        for(j=1;j<=n;j++)
11        {
12            if(i==j)a[i][j]=0;
13            else a[i][j]=max;
14        }
15}
16
17void bellman_ford()
18{
19    int i,j,k;
20    for(i=1;i<=n;i++)dis[i]=max;
21    dis[A]=0;
22    for(i=1;i<n;i++)
23    {
24        for(j=1;j<=n;j++)
25            for(k=1;k<=n;k++)
26            {
27                if(j==k)continue;
28                if(dis[k]>dis[j]+a[j][k])
29                    dis[k]=dis[j]+a[j][k];
30            }
31    }
32}
33
34int main()
35{
36    scanf("%d%d%d",&n,&A,&B);
37    init();
38    for(i=1;i<=n;i++)
39    {
40        scanf("%d",&k);
41        for(j=1;j<=k;j++)
42        {
43            scanf("%d",&t);
44            if(j==1)a[i][t]=0;
45            else a[i][t]=1;
46        }
47    }
48    bellman_ford();
49    if(dis[B]==max)printf("-1\n");
50    else printf("%d\n",dis[B]);
51    return 0;
52}
53
54
55

posted on 2009-07-24 19:07 蜗牛也Coding 阅读(303) 评论(2)  编辑 收藏 引用

评论

# re: pku 1847 2009-09-10 18:02 Johnnx

if(j==1)a[i][t]=0;
你代码里的这一句是什么意思，我不太明白？但却是必须的。能给我解释一下吗  回复  更多评论   

# re: pku 1847 2009-09-11 01:37 蜗牛也Coding

Switch in the i-th intersection is initially pointing in the direction of the first intersection listed.
注意题目中的这句话  回复  更多评论   


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


<2009年9月>
日一二三四五六
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜