//见笑
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int N[105];
int d[103],vis[103];
int p,mx;
struct stu
{
    int ne,val;
    stu *next;
}Node[103];
void inser(int x,int y,int z)
{
    stu *q;
    q=new stu;
    q->ne=y;
    q->val=z;
    q->next=Node[x].next;
    Node[x].next=q;
}
struct cmp
{
    bool operator () (const int &a,const int &b)
    {
        return d[a]>d[b];
    }
};
priority_queue<int,vector<int>,cmp> cc;
int djs(int s)
{
    int i,x,y,sum=0,t=0;
    stu *q;
    while(!cc.empty())
        cc.pop();
    for(i=1;i<=p;i++)
        d[i]=2000;
    memset(vis,0,sizeof(vis));
    vis[s]=1,d[s]=0;
    cc.push(s);
    mx=0;
    //cout<<"%$%$%$%$"<<s<<endl;
    while(!cc.empty())
    {
        x=cc.top();
        cc.pop();
        vis[x]=0;
        //cout<<x<<"    "<<d[x]<<endl;
        sum=sum+d[x];
        if(mx<d[x])
            mx=d[x];
        t++;
        q=Node[x].next;
        while(q!=NULL)
        {
            y=q->ne;
            if(d[y]>d[x]+q->val)
            {
                d[y]=d[x]+q->val;
                if(vis[y]==0)
                {
                    vis[y]=1;
                    cc.push(y);
                }
            }
            q=q->next;
        }
    }
    if(t<p)
        sum=2000000000;
    return sum;
}
int main()
{
    int i,j,s,x,y,z,min,t,ma;
    //freopen("in","r",stdin);
    while(cin>>p&&p!=0) 
    {
        memset(Node,0,sizeof(Node));
        memset(N,0,sizeof(N));
        t=0;
        for(i=1;i<=p;i++)
        {
            cin>>x;
            for(j=0;j<x;j++)
            {
                cin>>y>>z;    
                N[y]=1;
                inser(i,y,z);
            }
        }
        for(i=1;i<=p;i++)
        {
            if(Node[i].next==NULL&&N[y]==0)
            {
                cout<<"disjoint"<<endl;
                break;
            }
        }
        if(i<=p)
        {
            continue;
        }
        int min=2000000000;
        for(i=1;i<=p;i++)
        {
            s=djs(i);
            //cout<<i<<"    "<<s<<endl;
            if(s<min)
            {
                min=s;
                j=i;
                ma=mx;
            }
        }
        cout<<j<<" "<<ma<<endl;
    }
}

• 不是 0 K 的 (2580) luckylh 2010-04-12 15:00:56