纠结在这句话了If it is impossible to get from some town to some other town, print "Send Kurdy" instead. Put an empty line after each test case.
题目要求是如果一旦存在一个点不能到达另一个点就输出Send Kurdy
注意处理时跳过边长超过10的再跑FLOYD。之后在所有最短路中查找最大值即可
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} #define MAXN 105 double dp[MAXN][MAXN]; int x[MAXN],y[MAXN]; int N; int main() { //freopen("sample.txt","r",stdin); int T,kase = 1; scanf("%d",&T); while (T--) { scanf("%d",&N); for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) dp[i][j] = 10000000.0; for (int i = 1; i <= N; i++) scanf("%d%d",&x[i],&y[i]); for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) { double tmp = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) *(y[i] - y[j]); if (tmp > 100.0) continue; dp[i][j] = min(dp[i][j],sqrt(tmp)); } for (int k = 1; k <= N; k++) for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]); double ans = 0.0; for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) { ans = max(ans,dp[i][j]); } printf("Case #%d: ",kase++); if (ans == 10000000.0) puts("Send Kurdy"); else printf("%.4lf ",ans); putchar(' '); } return 0; }