题目大意如下
在一个二维坐标系中，有n个城市，坐标给出来了，然后有p个士兵要去占领这n个城市，但是路上有m个路障，都是线段，士兵不能越过路障前进。
每个士兵都有相同容量大小的一个干粮袋，每到一个城市他就能补充满自己的干粮袋。中途走路时走一个单位长度就消耗一个单位的干粮。
现在问的是这些个干粮袋最小的容量是多少，前提是保证p个士兵能占领完这n个城市，城市被占领顺序也是题目给好的，必须遵守
思路：P个士兵占领n个城市，可以看成p个士兵走出了p个路径，覆盖了所有的点。 但是题目没要求每个士兵都必须去占领。 也就是只要最小路径覆盖小于等于p个就代表所有的城市能被p个士兵去占领了。
最小路径覆盖的要求之一就是有向，无环，在题目中的体现就是城市被占领时必须有顺序。
这就符合一个拓扑序列了。所以就可以进行最小路径覆盖
然后整体的步骤就是，刚开始把各个点之间的距离先算出来，因为有障碍，所以必须把这些线段的两个端点都加入到点集中一块算，预处理两点距离时，就看两点之间有没有线段挡着，挡着就先按不可达算，注意处理线段交的时候端点相交不要管，因为还是可以过去。 没挡着就按照直线距离算。 然后floyd处理一下，任意两点之间的距离就算出来了
算出来后我们就要求干粮袋的容量了，一般的方法就是二分求可行性。
对于二分的一个值，我们就建立一遍图，任意两点的距离不大于这个值才可以连边。
当然注意我们是按照题目中给的那个占领顺序，前边的可以向后边的连边，反之不能
然后求路径覆盖。判断是否可行
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define eps 1e-8
#define MAXN 333
#define INF 1111111111
using namespace std;
typedef double TYPE;
struct POINT
{TYPE x;TYPE y;POINT() : x(0), y(0) {};POINT(TYPE _x_, TYPE _y_) : x(_x_), y(_y_) {};bool operator == (const POINT &p)const{return (fabs(x - p.x) < eps && fabs(y - p.y) < eps);}
}p[MAXN];
TYPE Distance(const POINT & a, const POINT & b)
{return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
struct SEG
{POINT a; //起点POINT b; //终点SEG() {};SEG(POINT _a_, POINT _b_):a(_a_),b(_b_) {};bool operator == (const SEG &p)const{return (p.a == a && p.b == b) || (p.b == a && p.a == b);}
}seg[MAXN];
TYPE Cross(const POINT & a, const POINT & b, const POINT & o)
{return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
bool IsIntersect(const SEG & u, const SEG & v)
{return (Cross(v.a, u.b, u.a) * Cross(u.b, v.b, u.a) > 0) &&(Cross(u.a, v.b, v.a) * Cross(v.b, u.b, v.a) > 0) &&(max(u.a.x, u.b.x) > min(v.a.x, v.b.x)) &&(max(v.a.x, v.b.x) > min(u.a.x, u.b.x)) &&(max(u.a.y, u.b.y) > min(v.a.y, v.b.y)) &&(max(v.a.y, v.b.y) > min(u.a.y, u.b.y));
}
int seq[MAXN];
struct node
{int v, next;
}edge[MAXN * MAXN];
int e, head[MAXN], mark[MAXN], cx[MAXN], cy[MAXN], n, m, so;
double dis[MAXN][MAXN];
void insert(int x, int y)
{edge[e].v = y;edge[e].next = head[x];head[x] = e++;
}
int path(int u)
{for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;if(!mark[v]){mark[v] = 1;if(cy[v] == -1 || path(cy[v])){cx[u] = v;cy[v] = u;return 1;}}}return 0;
}
int gao()
{int ans = 0;memset(cx, -1, sizeof(cx));memset(cy, -1, sizeof(cy));for(int i = 1; i <= n; i++){memset(mark, 0, sizeof(mark));ans += path(i);}return ans;
}
void floyd(int n)
{for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(dis[i][k] + dis[k][j] < dis[i][j])dis[i][j] = dis[i][k] + dis[k][j];
}
bool ok(double mid)
{e = 0;memset(head, -1, sizeof(head));for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++)if(dis[seq[i]][seq[j]] <= mid)insert(seq[i], seq[j] + n);int x = gao();if(n - x <= so) return true;return false;
}
void slove()
{double l = 0, r = INF;double ans = -1;while(r - l > eps){double mid = (l + r) / 2;if(ok(mid)) {ans = mid; r = mid;}else l = mid;}printf("%.2f\n", ans);
}
int main()
{int T;scanf("%d", &T);while(T--){scanf("%d%d%d", &n, &m, &so);for(int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);for(int i = 1; i <= m; i++){scanf("%lf%lf%lf%lf", &seg[i].a.x, &seg[i].a.y, &seg[i].b.x, &seg[i].b.y);p[n + i * 2 - 1] = seg[i].a;p[n + i * 2] = seg[i].b;}for(int i = 1; i <= n; i++) scanf("%d", &seq[i]);for(int i = 1; i <= n + m * 2; i++)for(int j = 1; j <= n + m * 2; j++){if(i == j) {dis[i][j] = 0; continue;}int flag = false;for(int k = 1; k <= m; k++){if(seg[k] == SEG(p[i], p[j])) continue;if(IsIntersect(seg[k], SEG(p[i], p[j]))){flag = true;break;}}if(flag) dis[i][j] = INF;else dis[i][j] = Distance(p[i], p[j]);}floyd(n + m * 2);slove();}return 0;
}