Algorithm 版 (精华区)

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: 1298K-DominoEffect-ZJU
发信站: 哈工大紫丁香 (2002年10月11日11:26:09 星期五), 站内信件

按照图的连接找出每个点的最短路径，
得到时间值最大点
再找出时间值最大边

#include <math.h>
#include <stdio.h>
#include <string.h>
struct node
{
    node*   next;
    int     index;
    int     len;
};
int go(node* link,int* value,int index)
{
    node* p,* q;
    q=p=&link[index];
    while(p->next!=NULL)
    {
        p=p->next;
        if(value[p->index]>p->len+value[index]) 
        {
            value[p->index]=p->len+value[index];
            go(link,value,p->index);
        }
    }
    return 0;
}
int main(int argc, char* argv[])
{
#ifndef ONLINE_JUDGE
    freopen("data.in","r",stdin);
#endif
    int p1,p2,f1,time=0;
    int m,n,i,j,k,start,end,len;
    node* p,* q;
    float max;
    while(scanf("%d %d",&n,&m),n!=0)
    {
        node* link=new node[n];
        int* value=new int[n];
        for(i=0;i<n;i++) link[i].next=NULL;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&start,&end,&len);
            p=&link[start-1];
            while(p->next!=NULL) p=p->next;
            q=new node[1];q->next=NULL;q->len=len;q->index=end  -1;p->next=q;
            p=&link[end  -1];
            while(p->next!=NULL) p=p->next;
            q=new node[1];q->next=NULL;q->len=len;q->index=start-1;p->next=q;
        }
        for(i=0;i<n;i++) value[i]=10000000;value[0]=0;
        go(link,value,0);
        p1=0;p2=0;f1=1;max=0;
        for(i=0;i<n;i++) if(max<value[i]){ max=value[i];p1=i;}
        for(i=0;i<n;i++)
        {
            q=p=&link[i];
            while(p->next!=NULL)
            {
                p=p->next;
                if((float)(p->len+value[i]+value[p->index])/2>max)
                {
                    max=(float)(p->len+value[i]+value[p->index])/2;
                    f1=0;p1=i;p2=p->index;
                }
            }
        }
        printf("System #%d\n",++time);
        printf("The last domino falls after %.1f seconds, ",max);
        if(f1)  printf("at key domino %d.\n\n",1+p1);
        else    printf("between key dominoes %d and 
%d.\n\n",1+(p1<p2?p1:p2),1+(p1>p2
?p1:p2));
    }
    return 0;
}
 
--
RULE 1 - Life is not fair, get used to it.

                                     ——Bill Gates

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.249.235]
※ 修改:·Lerry 於 10月11日11:30:15 修改本文·[FROM: 202.118.249.235]