题意：有N个点，给定M个集合，集合Si里面的点两两之间的距离都为Ti，集合里面的所有点数之和<=1e6。有两个人分别在1和N处，求1个点使得两个人到这一点距离的最大值最小

思路：这题是裸的最短路问题，难点在建图。然而建图也只有1步，在集合外新建1个点，每个点向它连一条Ti/2的边（避免浮点数，可以先乘2，然后结果除以2）。如此巧妙。。。

#include 
     
      using namespace std;#define X first#define Y second#define pb(x) push_back(x)#define mp(x, y) make_pair(x, y)#define all(a) (a).begin(), (a).end()#define mset(a, x) memset(a, x, sizeof(a))#define mcpy(a, b) memcpy(a, b, sizeof(b))#define cas() int T, cas = 0; cin >> T; while (T --)template
      
       bool umax(T&a, const T&b){return a
       
        
         bool umin(T&a, const T&b){return b
         
           pii;#ifndef ONLINE_JUDGE    #include "local.h"#endifconst int N = 1e6 + 7;struct Edge {    int u, v, w;    int next;    Edge(int u, int v, int w) {        this->u = u;        this->v = v;        this->w = w;    }    Edge() {}};int SZ;int head[N];Edge edge[N << 1];ll d1[N], dn[N];int n, m, nn;bool used[N];void add(int u, int v, int w) {    edge[SZ] = Edge(u, v, w);    edge[SZ].next = head[u];    head[u] = SZ ++;}void spfa(int s, ll d[]) {    queue
          
            Q; for (int i = 1; i <= nn; i ++) d[i] = pow(10, 18) + 7; d[s] = 0; mset(used, 0); Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); used[u] = false; for (int i = head[u]; ~i; i = edge[i].next) { Edge e = edge[i]; if (umin(d[e.v], d[u] + e.w)) { if (!used[e.v]) { Q.push(e.v); used[e.v] = true; } } } }}int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout);#endif // ONLINE_JUDGE int t, s, u; cas() { printf("Case #%d: ", ++ cas); cin >> n >> m; nn = n; mset(head, -1); SZ = 0; for (int i = 0; i < m; i ++) { scanf("%d%d", &t, &s); nn ++; for (int j = 0; j < s; j ++) { scanf("%d", &u); add(u, nn, t); add(nn, u, t); } } spfa(1, d1); spfa(n, dn); ll mind = pow(10, 18); bool yes = false; vector
           
             ans; for (int i = 1; i <= n; i ++) { if (umin(mind, max(d1[i], dn[i]))) yes = true; } if (!yes) { puts("Evil John"); continue; } cout << mind / 2 << endl; for (int i = 1; i <= n; i ++) { if (max(d1[i], dn[i]) == mind) { ans.pb(i); } } sort(all(ans)); for (int i = 0; i < ans.size(); i ++) { printf("%d%c", ans[i], i == ans.size() - 1? '\n' : ' '); } } return 0;}