题意：有N个点，两个人，其中一个人住在点1，另一个人住在点n，有M个点集，集合内的数表示任意两点的距离为dis ，现在问，如果两个人要见面，
需要最短距离是多少，有哪几个点能被当成见面点。
析：分别对1和n进行最短路操作，这个题最让人别扭的就是边太多，如果你直接全部都存下来，那么一定会MLE，所以一定要优化边。所以我们要把每一行的边都记下来，
而不是两两都记下，然后把每一行的编号记下来，最后要查询时，就行编号去定位到哪一行，这样就不会超内存。这里会了，其他的就很简单了。
代码如下：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <stack>
using namespace std; typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const LL LNF = 100000000000000000;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const char *mark = "+-*";
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
int n, m;
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
inline LL Max(LL a, LL b){ return a < b ? b : a; }
inline LL Min(LL a, LL b){ return a > b ? b : a; }
vector<int> G[maxn];
vector<int> b[maxn];
LL d1[maxn];
LL d2[maxn];
int t[maxn];
bool vis[maxn]; void dijstra(int s, LL* d){
priority_queue<P, vector<P>, greater<P> > pq;
pq.push(P(0, s));
memset(vis, false, sizeof vis);
fill(d, d+n+1, LNF);
d[s] = 0; while(!pq.empty()){
P p = pq.top(); pq.pop();
int u = p.second;
if(d[u] < p.first) continue;
for(int i = 0; i < b[u].size(); ++i){//从编号找出在哪行
int v = b[u][i];
if(vis[v]) continue;
vis[v] = true;
for(int j = 0; j < G[v].size(); ++j){
int uv = G[v][j], w = t[v];
if(d[uv] > d[u] + w){
d[uv] = d[u] + w;
pq.push(P(d[uv], uv));
}
}
}
}
} int main(){
int T; cin >> T;
for(int kase = 1; kase <= T; ++kase){
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i) G[i].clear(), b[i].clear();
for(int i = 1; i <= m; ++i){
int k;
scanf("%d %d", &t[i], &k);
for(int j = 0; j < k; ++j){
int v;
scanf("%d", &v);
G[i].push_back(v);//存边
b[v].push_back(i);//记下行号
}
} dijstra(1, d1);
dijstra(n, d2);
printf("Case #%d: ", kase);
LL ans = LNF;
for(int i = 1; i <= n; ++i)
ans = Min(ans, Max(d1[i], d2[i]));
if(ans == LNF) puts("Evil John");
else{
printf("%I64d\n", ans);
int cnt = 0;
for(int i = 1; i <= n; ++i)
if(ans == Max(d1[i], d2[i])){
if(cnt) putchar(' ');
printf("%d", i);
++cnt;
}
printf("\n");
}
}
return 0;
}