pku 1135

2009年7月29日

题目链接：PKU 1135 Domino Effect

分类：（Dijkastra+枚举）  

题目分析与算法原型
         这道题目的意思大致是给你n个骨牌，以及某些骨牌之间的边，这些边的权值代表，从这条边的某一端（某一骨牌）开始倒，一直倒到该边的终点（该边的另一个骨牌）所需的时间，然后题目的求的是，从编号为1的骨牌开始倒（注意，某一个骨牌倒的时候，连同与其相邻的边都同时开始往外面倒），求最后倒的骨牌的位置（在某两个骨牌之间或者是刚给你的n个骨牌的其中一个）并输出时间..........
         其实，因为每个牌倒的同时都连带与其连接的所有边也同时倒，不难看出，当从骨牌1一直倒到某个骨牌x的时候，其实从1到x间的路径必定是最短路径，因为肯定是沿着最短的路径才能先到达x么，考虑到这点，问题就已经解决一半了，我们可以先算出从1点出发的到其他所有点的最短路径，然后取这些最短路径中最长的那个点y，然后再枚举所有与这个点相邻的点      （这里需要除去 path[y]这点），假设z是其中一个点，然后找能使得(dis[y]+dis[z]+map[y][z])/2最长的那个点,若(dis[y]+dis[z]+map[y][z])/2>dis[y],则说明最后一个是y,若(dis[y]+dis[z]+map[y][z])/2=dis[y]则说明,最后一个处与y和z之间.........

Code:

  1#include<stdio.h>
  2#define max 1000000000
  3#define len 505
  4
  5int n,m,a,b,l,map[len][len],dis[len],visit[len],path[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)map[i][j]=0;
 14            else map[i][j]=max;
 15        }
 16}
 17void Dijkastra(int s)//s为源点
 18{
 19    int i,j;
 20    for(i=1;i<=n;i++)
 21    {
 22        dis[i]=map[s][i];
 23        visit[i]=0;
 24        if(i!=s&&dis[i]<max)path[i]=s;
 25        else path[i]=-1;
 26
 27    }
 28    visit[s]=1;
 29    for(i=1;i<n;i++)
 30    {
 31        int min=max,u;
 32        for(j=1;j<=n;j++)
 33            if(visit[j]==0&&dis[j]<min)
 34            {
 35                u=j;
 36                min=dis[j];
 37            }
 38
 39            if(min==max)return;//此语句对于非连通图是必须的，表示当前已经不存在路径了
 40
 41            visit[u]=1;
 42            for(j=1;j<=n;j++)
 43                if(visit[j]==0&&map[u][j]<max&&dis[u]+map[u][j]<dis[j])
 44                {    
 45                    dis[j]=dis[u]+map[u][j];
 46                    path[j]=u;
 47                }
 48    }
 49}
 50int main()
 51{
 52    int i,ccase=1;;
 53    while(scanf("%d%d",&n,&m)!=EOF)
 54    {
 55        if(n==0&&m==0)break;
 56        init();
 57        for(i=0;i<m;i++)
 58        {
 59            scanf("%d%d%d",&a,&b,&l);
 60            if(l<map[a][b])
 61            {
 62                map[a][b]=l;
 63                map[b][a]=l;
 64            }
 65        }
 66        Dijkastra(1);
 67        int _max=-1,num;
 68        for(i=1;i<=n;i++)
 69        {
 70            if(dis[i]>_max)
 71            {
 72                _max=dis[i];
 73                num=i;
 74            }
 75        }
 76        _max=-1;
 77        int pos;
 78        for(i=1;i<=n;i++)
 79        {
 80            if(i!=path[num]&&map[num][i]<max)
 81            {
 82                if(dis[num]+dis[i]+map[num][i]>_max)
 83                {
 84                    _max=dis[num]+dis[i]+map[num][i];
 85                    pos=i;
 86                }
 87            }
 88        }
 89        printf("System #%d\n",ccase++);
 90        if(dis[pos]+map[num][pos]==dis[num])
 91            printf("The last domino falls after %.1f seconds, at key domino %d.\n",(double)dis[num],num);
 92        else
 93        {
 94            double res=(double)(dis[pos]+map[num][pos]+dis[num])/2;
 95            if(num<pos)
 96                printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n",res,num,pos);
 97            else
 98                printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n",res,pos,num);
 99
100        }
101        printf("\n");
102
103    }
104    return 0;
105}
106

posted on 2009-07-29 10:14 蜗牛也Coding 阅读(262) 评论(0)  编辑 收藏 引用


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


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜