题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5521
#include<bits/stdc++.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
const int maxn =2e5+5;
const int mod=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;ll powmod(ll x,ll y) {ll t;for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod;return t;}
ll gcd(ll x,ll y) { return y==0?x:gcd(y,x%y); }
/*
题目大意：给定一系列团的结构，
然后按照这样的图结构，进行最短路的询问，
问1和n点要约到哪个点进行见面才能使时间最短。最短路的变种，下面详解这道题，
首先对于一个点来说，可以以该点所在团来扩张，比如
i点在j1,j2,j3团中，那么其相邻边就是团中的各个点，
最短路中有两个绕人的东西就是，
vis标记数组，和距离压缩。这道题中，首先很明显，走过的点就没必要再走了，因为是最小堆，
每次都拿出最小的距离点来扩展的。
然后团也有相应的标记数组，因为一个团如果已经被利用进行差分约束过后，
其效果和点也是一样的，同样是用最短的来进行约束，
因为团中任意两点之间的最短路是一样的。
*/vector<int> bk[maxn],st[maxn];///bk代表是团的集合，st代表是边的集合
int val[maxn],p;///i团之间的距离struct node
{int u;ll d;bool operator<(const node& y) const{return d>y.d;///最小堆}
};int n,m,x;
int vis[maxn],used[maxn];
ll d1[maxn],d2[maxn];///团是否遍历过,用来差分的距离数组
void dij(int s,ll * dis)
{memset(vis,0,sizeof(vis));memset(used,0,sizeof(used));for(int i=1;i<=n;i++) dis[i]=INF;priority_queue<node> pq;pq.push(node{s,0});dis[s]=0;///初始化while(!pq.empty()){node tp=pq.top(); pq.pop();int u=tp.u;if(used[u]) continue;used[u]=1;///标记for(int i=0;i<st[u].size();i++)///遍历这个点的所有所在团{int id=st[u][i];if(vis[id]) continue; vis[id]=1;///团的记号for(int j=0;j<bk[id].size();j++)///遍历每个团的每个点{int v=bk[id][j];if(v==u) continue;if(dis[u]+val[id]>=dis[v]) continue;///不满足约束的直接跳过dis[v]=dis[u]+1LL*val[id];pq.push(node{v,dis[v]});}}}
}int main()
{int t;scanf("%d",&t);for(int ca=1;ca<=t;ca++){scanf("%d%d",&n,&m);for(int i=0;i<=max(n,m);i++) { bk[i].clear();st[i].clear(); }///清空初始化for(int i=0;i<m;i++){scanf("%d",&val[i]);scanf("%d",&p);for(int j=1;j<=p;j++){scanf("%d",&x);bk[i].push_back(x);///i团中有多少个点st[x].push_back(i);///x点属于哪个团}}memset(d1,0,sizeof(d1));memset(d2,0,sizeof(d2));dij(1,d1); dij(n,d2);///两遍dij算法ll ans=INF; for(int i=1;i<=n;i++) ans=min(ans,max(d1[i],d2[i]));printf("Case #%d: ",ca);if(ans==INF) { puts("Evil John");continue; }else printf("%lld\n",ans);int st[maxn],cnt=0;for(int i=1;i<=n;i++) if(max(d1[i],d2[i])==ans) st[cnt++]=i;for(int i=0;i<cnt;i++) printf("%d%c",st[i],i==cnt-1?'\n':' ');}return 0;
}