Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## floyd水题，注意不连通时将边设置为INF就行

Posted by cedricgsh55 at 2019-04-06 11:13:41 on Problem 1125
```#include<iostream>
#include<algorithm>
int inf = 300000;
using namespace std;
int n;
int map[105][105];
void floyd()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
//cout << i << "--->" << j << " " << map[i][j] << endl;
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
//cout << i << "--->" << j << " " << map[i][j] << endl;
}

}
int main()
{
while (cin >> n, n)
{
//memset(map, inf, sizeof(map));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
map[i][j] = (i == j ? 0 : inf);
//cout << map[1][2] << endl;
for (int i = 1; i <= n; i++)
{
int num;
cin >> num;
for (int j = 1; j <= num; j++)
{
int t;
cin >> t;
cin >> map[i][t];
}
}
/*
cout << "开始运算前" << endl;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << map[i][j] << " ";
cout << endl;

}*/
floyd();
int min_time = inf;
int mins;
int tar;
for (int i = 1; i <= n; i++)
{
int flag = 0;
mins = 0;
for (int j = 1; j <= n; j++)
{
if (map[i][j] == inf)
{
flag = 1;
continue;
}
else if (map[i][j] > mins)
mins = map[i][j];
}
if (flag)
continue;
else if (mins < min_time)
{
min_time = mins;
tar = i;
}

}
cout << tar << " " << min_time << endl;

}

system("pause");
return 0;
}```

Followed by: