Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

过掉的高手来帮忙看看啊~ 不胜感激````

Posted by apple_SCUT at 2005-09-13 01:07:30 on Problem 2607
不知道哪里错了,算法就是求出所有点对间的最短路,然后枚举fire放置点

#include <stdio.h>
#define maxint 2147483647
int f,n;
int fire[101];
int a[501][501];
int d[501][501];
char v[501];
int main()
{int i,j,t,k,max,min,tmax,ans;
    scanf("%d%d",&f,&n);
    for(i=1;i<=f;i++) 
    {
        scanf("%d",&fire[i]);
        v[fire[i]]=1;
    }    
    while (scanf("%d %d %d",&i,&j,&t)==3)
    {
        if (!a[i][j] || a[i][j]>t) 
        {
            a[i][j]=t;
            a[j][i]=t;
        }
    }
    for(i=1;i<=n;i++) 
        for(j=1;j<=n;j++) if (a[i][j]) d[i][j]=a[i][j]; 
    for(i=1;i<=n;i++) d[i][i]=0;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if (i==j) continue;
                if ((d[i][j]>d[i][k]+d[k][j]) || (!d[i][j] && d[i][k]+d[k][j]>0)) 
                            d[i][j]=d[i][k]+d[k][j];
            }    
    max=maxint;
    for(k=1;k<=n;k++) if (!v[k])
    {
        fire[0]=k;
        tmax=0;
        for(i=1;i<=n;i++) 
        {
            min=maxint;
            for(j=0;j<=f;j++) if (d[i][fire[j]]<min) min=d[i][fire[j]];
            if (min>tmax) tmax=min;
        }
        if (tmax<max) 
        {
            max=tmax;
            ans=k;
        }
    }
    printf("%d",ans);
    return 0;
}            

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator