#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n,cost[101][101],dis[101],vis[101];
const int inf=0x3f3f3f3f;
int dijkstra(int s)
{
    memset(vis,0,sizeof(vis));
    int i,j;
    for(i=1;i<=n;i++)
    {
        if(i==s)dis[i]=0;
        else dis[i]=cost[s][i];
    }
    vis[s]=1;
    for(i=1;i<=n;i++)
    {
        int t=inf,k;
        for(j=1;j<=n;j++)
        {
            if(vis[j]==0&&dis[j]<t)
                t=dis[j],k=j;
        }
        if(t==inf)break;
        vis[k]=1;
        for(j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[k]+cost[k][j]<dis[j])
                dis[j]=dis[k]+cost[k][j];
        }
    }
    int ans=-1;
    for(i=1;i<=n;i++)
    {
        if(i==s)continue;
        if(dis[i]>ans)ans=dis[i];
    }
    return ans;
}
int main()
{
    while(scanf("%d",&n)&&n!=0)
    {
        int i,j,k,con,p,t;
        for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
            cost[i][j]=inf;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&con);
            for(j=1;j<=con;j++)
            {
                scanf("%d%d",&p,&t);
                cost[i][p]=t;
            }
        }
        int ans=inf;
        for(i=1;i<=n;i++)
        {
            int res=dijkstra(i);
            if(res==-1)
            {
                ans=-1;break;
            }
            else if(res<ans)ans=res,k=i;
        }
        if(ans!=inf)printf("%d %d\n",k,ans);
        else printf("disjoint\n");
    }
    return 0;
}

• Re:确实水~0ms...dijkstra (1676) wqx 2024-05-29 08:53:41
• Re:确实水~0ms...dijkstra (1676) wqx 2024-05-29 08:53:42