題目描述：
眾所周知，證券經紀業依靠的就是過度的傳言。您需要想出股票經紀人中傳播假情報的方法，讓您的雇主在股票市場的占據優勢。為了獲得最大的效果，你必須蔓延最快的方式謠言。不幸的是你，股票經紀人信息只信任他們的“可靠來源”，這意味著你在你傳播謠言之前必須考慮到他們的接觸結構。它需要特定股票經紀人和一定的時間把謠言傳遞給他的每一位同事。你的任務將是寫一個程序，告訴您選擇哪一個股票經紀人作為謠言的出發點和所花費多少時間將謠言擴散到整個社會的股票經紀人。這一期限是衡量過去的人收到信息所需的時間。
輸入
你的程序包含多組股票經紀人的輸入數據。每組以股票經紀人的人數開始。接下來的幾行是每個經紀人與其他人接觸的一些信息，包括這些人都是誰，以及將訊息傳達到他們所需的時間。每個經紀人與其他人接觸信息的格式如下：開頭的第一個數表示共有n個聯系人，接下來就有n對整數。每對整數列出的第一個數字指的是一個聯系人（例如，一個'1'是指編號1的人），其次是在傳遞一個信息給那個人時所采取分鐘的時間。沒有特殊的標點符號或空格規則。每個人的編號為1至經紀人數目。所花費的傳遞時間是從1到10分鐘（含10分種）。股票經紀的人數范圍是從1到100。當輸入股票經紀人的人數為0時，程序終止。
輸出
在對於每一組數據，你的程序必須輸出一行，包括的信息有傳輸速度最快的人，以及在最後一個人收到消息後，所總共使用的時間（整數分鐘計算）。你的程序可能會收到的一些關系會排除一些人，也就是有些人可能無法訪問。如果你的程序檢測到這樣一個破碎的網絡，只需輸出消息“disjoint”。請注意，所花費的時間是從A傳遞消息到B，B傳遞信息到A不一定是花費同樣的傳遞時間，但此類傳播也是可能的。
思路：遍歷每個節點，求出這個節點到其他節點的最短時間，再從這些最短的時間中選出最大的那個，再從這些最大的時間中選出最小的那個。（呵呵，有點繞口）
看代碼：
[cpp]
#include<iostream>
using namespace std;
int n;//節點個數
int map[101][101];//存儲邊
bool v[101];//標記數組
int dis[101];//起點傳播到相應節點的傳播時間
int data[101];//節點傳播的最長時間
int qian[101];//記錄傳播中節點的前驅結點
int dij(int form)//求最短時間
{
int i,j,k=0;
/* 初始化相應的數組*/
memset(v,0,101);
for(i=1;i<=n;i++){data[i]=0;dis[i]=10000000;qian[i]=i;}
for(i=1;i<=n;i++)
if(!v[i]&&map[form][i]){dis[i]=map[form][i];qian[i]=form;}
v[form]=1;
/*=================*/
int sum=0;//記錄最短時間
int num=1;//記錄遍歷的節點個數
for(i=1;i<n;i++)
{
int min=100000;
for(j=1;j<=n;j++)if(!v[j]&&min>dis[j]){min=dis[j];k=j;}
if(min==100000)break;//如果min值沒改變則圖中有獨立節點
v[k]=1;
if(min>data[qian[k]])
{
/*如果min大於前驅節點傳播的最大時間，則只需加上min和data[qian[k]]的差，修改前驅節點傳播最大時間
如果min小於前驅結點的傳播最大時間，則總傳播時間不變*/
sum+=min-data[qian[k]];
data[qian[k]]=min;
}
num++;
for(j=1;j<=n;j++)
{
if(!v[j]&&map[k][j])
if(dis[j]>map[k][j]+dis[k]){dis[j]=map[k][j]+dis[k];qian[j]=qian[k];}
}
}
if(num!=n)return 10000000;//圖中有獨立節點
else return sum;
}
int main()
{
while(scanf("%d",&n))
{
if(n==0)break;
memset(map,0,sizeof(map));
int i,j,k,to,w;
for(i=1;i<=n;i++)
{
cin>>j;
for(k=1;k<=j;k++)
{
cin>>to>>w;
map[i][to]=w;
}
}
int form=0,min_time=1000000;
for(i=1;i<=n;i++)
{ www.2cto.com
k=dij(i);
if(min_time>k){min_time=k;form=i;}
}
if(form==0)cout<<"disjoint"<<endl;//圖中有鼓勵節點
else cout<<form<<" "<<min_time<<endl;
}
return 0;
}
