PersonalCorpus 版 (精华区)

40645 2002-10-11 11:12:24 Accepted
1298 C++ 00:00.03 1716K Big Guava

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <math.h>
#include <ctype.h>

int dl[500][500];
int b[500];
int l[500000][3];

void dijkstra (int from, int n)
{
    int best, best_j, i, j;
    bool mark[500];

    memset(mark,0,sizeof(mark));
    mark[from]=true; b[from]=0;
    do {
        best=0;
        for (i=0;i<n;i++) if (mark[i]) for (j=0;j<n;j++)
            if ((!mark[j])&&(dl[i][j]!=0)) if 
((best==0)||(b[i]+dl[i][j]<best)) {
                best=b[i]+dl[i][j];
                best_j=j;
            }
        if (best!=0) {
            b[best_j]=best;
            mark[best_j]=true;
        }
    } while (best!=0);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("c:\\0acm\\zju\\i1298","r",stdin);
    freopen("c:\\0acm\\zju\\o1298","w",stdout);
#endif

    int i,j,k,n,m,c,d,e,t=0;
    double res,temp;

    while (1) {
        scanf("%d%d\n",&n,&m);
        if ((n==0)&&(m==0)) break; else t++;
        memset(dl,0,sizeof(dl));
        for (i=0;i<m;i++) {
            scanf("%d%d%d\n",&c,&d,&e); c--; d--;
            if ((dl[c][d]==0)||(dl[c][d]>e)) {  dl[c][d]=e; dl[d][c]=e;
 }
            l[i][0]=c; l[i][1]=d; l[i][2]=e;
        }
        dijkstra(0,n);
        k=0; for (i=1;i<n;i++) if (b[i]>b[k]) k=i;
        res=b[k]; c=-1;
        for (i=0;i<m;i++) if (abs(b[l[i][0]]-b[l[i][1]])<l[i][2]) {
            temp=((double)(l[i][2]-abs(b[l[i][0]]-b[l[i][1]]))) /2;
            if (b[l[i][0]]>b[l[i][1]]) temp+=b[l[i][0]];
                else temp+=b[l[i][1]];
            if (temp>res) {
                res=temp;
                c=l[i][0];
                d=l[i][1];
            }
        }
        printf("System #%d\n",t);
        if (c<0)
            printf("The last domino falls after %.1lf seconds, at key 
domino %d.\n\n",res,k+1);
        else
            printf("The last domino falls after %.1lf seconds, between 
key dominoes %d and %d.\n\n",res,c+1,d+1);
    }
}