a[j][k]=findMin(a[j][k],a[j][i]+a[i][k]);
i,j,k顺序错了会WA

#include<iostream>
#define SIZE 1012
#define INF (1<<30)
using namespace std;
int n,m,a[SIZE][SIZE];
int ans1,ans2,x,y;
void Init(void)
{
    for(int i=0;n-i>0;i++)
    {
        for(int j=0;n-j>0;j++)
        {
            a[i][j]=INF;
        }
    }
}
int findMin(int a,int b)
{
    return a<b?a:b;
}
int findMax(int a,int b)
{
    return a>b?a:b;
}
void floyd(void)
{
    for(int i=0;n-i>0;i++)
    {
        for(int j=0;n-j>0;j++)
        {
            for(int k=0;n-k>0;k++)
            {
                if(a[j][i]!=INF&&a[i][k]!=INF)
                {
                    a[j][k]=findMin(a[j][k],a[j][i]+a[i][k]);
                }
            }
        }
    }
}
void findAns(int &ans1,int &ans2)
{
    ans1=ans2=-1;
    for(int i=0;n-i>0;i++)
    {
        bool ok=true;
        int count1=-1,count2=-1;
        for(int j=0;n-j>0;j++)
        {
            if(i==j) continue;
            else if(a[i][j]==INF)
            {
                ok=false;
                break;
            }
            else if(a[i][j]>count2)
            {
                count1=i;
                count2=a[i][j];
            }
        }
        if(ok&&count2!=-1)
        {
            if(ans2==-1) ans1=count1,ans2=count2;
            else if(count2<ans2) ans1=count1,ans2=count2;
        }
    }
}    
void printInfo(void)
{
    for(int i=0;n-i>0;i++)
    {
        for(int j=0;n-j>0;j++)
        {
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
}   
int main()
{
    while(scanf("%d",&n),n)
    {
        Init();
        for(int i=0;n-i>0;i++)
        {
            scanf("%d",&m);
            for(int j=0;m-j>0;j++)
            {
                scanf("%d %d",&x,&y);
                a[i][x-1]=y;
            }
        }
        floyd();
        findAns(ans1,ans2);
        //printInfo();
        if(ans2==-1) printf("disjoint\n");
        else printf("%d %d\n",ans1+1,ans2);
    }
    return 0;
}

• 用memset时间怎么还长一点 (46) speedcell4 2011-08-19 01:12:14