题意：给出几个集合，每个集合中有Si个点 且任意两个点的距离为ti，现在要求两个人分别从1和n出发,问最短多长时间才能遇到,且给出这些可能的相遇点;
取两个人到达某点时所用时间大的值 然后取最小的 若有多个结果 则按点的升序排列
解析：
比较裸的最短路 ，但坑在建图上，Si的和小于1e6 那么建的边肯定会超内存 所以压缩一下，把每个集合看作一个点 集合中的点到集合的距离为0 集合到集合中的点的距离为ti 即入为0 出为ti 然后普通最短路求就好了
spfa：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = , INF = 0xfffffff;
typedef long long LL;
int n,m;
int d[maxn], head[maxn], vis[maxn],tran1[maxn], tran2[maxn];
struct time{
int sum,ix;
}Time[maxn]; int cmp(time a,time b)
{
if(a.sum == b.sum) return a.ix < b.ix;
return a.sum < b.sum;
} struct node{
int u,v,w,next;
}Node[maxn]; void add(int u,int v,int w,int i)
{
Node[i].u = u;
Node[i].v = v;
Node[i].w = w;
Node[i].next = head[u];
head[u] = i;
} void spfa(int s)
{
queue<int> Q;
fill(d,d+maxn,INF);
mem(vis,);
d[s] = ;
Q.push(s);
vis[s] = ;
while(!Q.empty())
{
int u = Q.front();Q.pop();
vis[u] = ;
for(int i=head[u]; i!=-; i=Node[i].next)
{
node e = Node[i];
if(d[e.v] > d[u] + e.w)
{
d[e.v] = d[u] + e.w;
if(!vis[e.v])
{
Q.push(e.v);
vis[e.v] = ;
}
}
}
}
}
int main()
{
int T;
int temp = ;
scanf("%d",&T);
while(T--)
{
mem(head,-);
mem(tran1,);
mem(tran2,);
mem(Time,);
int ans = ;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int t,h,tmp;
scanf("%d%d",&t,&h);
while(h--)
{
scanf("%d",&tmp);
add(tmp,n+i,,ans++);
add(n+i,tmp,t,ans++);
}
}
spfa();
for(int i=;i<=n;i++)
tran1[i] = d[i];
spfa(n);
for(int i=;i<=n;i++)
tran2[i] = d[i];
for(int i=;i<n;i++)
{
Time[i].sum = max(tran1[i+],tran2[i+]);
Time[i].ix = i+;
}
sort(Time,Time+n,cmp);
LL res = Time[].sum;
printf("Case #%d: ",++temp);
if(res == INF)
{
printf("Evil John\n");
continue;
}
printf("%I64d\n",res);
for(int i=;i<n;i++)
{
if(res == Time[i].sum)
{
if(i > ) printf(" ");
printf("%d",Time[i].ix);
}
else
break;
}
printf("\n");
} return ;
}