免费在线亚洲欧美,亚洲国产精品成人综合,亚洲精品日韩久久

P1125

FLOYD
一定要注意,floyd的本質(zhì)是動(dòng)態(tài)規(guī)劃

#include <iostream>

using namespace std;

const int MAXN=101;

int dist[MAXN][MAXN];

int max_[MAXN];

int main()

{

int n,m;

while(1)

{

cin>>n;

if (0==n) break;

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++)

dist[i][j]=0xffff;

memset(max_,0,sizeof(max_));

for (int i=1;i<=n;i++)

dist[i][i]=0;

for (int i=1;i<=n;i++)

{

cin>>m;

for (int j=1;j<=m;j++)

{

int to,temp;

cin>>to>>temp;

dist[i][to]=temp;

}

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++)

for (int k=1;k<=n;k++)

{

int dist_=dist[j][i]+dist[i][k];

if (dist[j][k]>dist_) dist[j][k]=dist_;

}

for (int i=1;i<=n;i++)

{

for (int j=1;j<=n;j++)

{

if (j==i) continue;

if (max_[i]<dist[i][j]) max_[i]=dist[i][j];

}

int min=0x7fffffff;

int k=0;

for (int i=1;i<=n;i++)

{

if (min>max_[i]) {min=max_[i];k=i;}

}

cout<<k<<" "<<min<<endl;

// system("pause");

}

return 0;

}

posted on 2009-10-05 11:28 Vincent 閱讀(101) 評(píng)論(0) 編輯收藏引用所屬分類(lèi): 數(shù)據(jù)結(jié)構(gòu)與算法

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: P3368 P2352 dinic P3273 P2104 ctsc2000 丘比特的煩惱 usaco 4.3 lgame P3267 P1276 P1837

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類(lèi)

隨筆檔案

文章檔案

Link

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

P1125