UVa 10803 - Thunder Mountain

传送门

UVa 10803 - Thunder Mountain

题意

给一个图,两地之间的距离不能超过10KM,否则就算不连通。

如果图式强联通的,输出两点之间最长路径。

思路

Floyd

不过想不明白题目给的那个公式是怎么用的

代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int MAXN = 100 + 5;
const int INF = 0x3f3f3f3f;
 
struct POINT
{
    int x, y;
}pit[MAXN];
 
double dis[MAXN][MAXN];
int n;
 
void Floyd()
{
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int T, i, j, cases = 0;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        double temp = 0;
        for (i = 0; i < n; i++)
        {
            scanf("%d%d", &pit[i].x, &pit[i].y);
            for (j = 0; j < i; j++)
            {
                temp = hypot(pit[i].x - pit[j].x, pit[i].y - pit[j].y);
                dis[i][j] = dis[j][i] = (temp > 10 ? INF : temp);
            }
        }
        Floyd();
        double ans = -1;
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                ans = max(ans, dis[i][j]);
        printf("Case #%d:\n", ++cases);
        ans == INF ? printf("Send Kurdy\n") : printf("%.4f\n", ans);
        printf("\n");
    }
    return 0;
}

Powered by Jekyll and Theme by solid