You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
84 lines
2.4 KiB
C++
84 lines
2.4 KiB
C++
#include <cstdio>
|
|
#include <cstring>
|
|
#include <cctype>
|
|
#include <map>
|
|
#include <vector>
|
|
using namespace std;
|
|
#define ll long long
|
|
const int N=2e5+50,M=N<<3;
|
|
bool inq[N+M];
|
|
ll dis1[N+M],dis2[N+M],que[N+M],d[N+M];
|
|
int head[N+M],nxt[N+M],len[N+M],to[N+M],ecnt;
|
|
inline void addEdge(int f,int t,int l)
|
|
{
|
|
//printf("Add from %d to %d len %d\n",f,t,l);
|
|
ecnt++;
|
|
nxt[ecnt] = head[f];
|
|
head[f] = ecnt;
|
|
to[ecnt] = t;
|
|
len[ecnt] = l;
|
|
}
|
|
void spfa(int s, ll *dis)
|
|
{
|
|
memset(inq, 0, sizeof(inq));
|
|
int h=0, t=0;
|
|
for (dis[s] = 0, que[t++] = s, inq[s] = true; h ^ t; inq[que[h++]] = false)
|
|
for (int cur = head[que[h]]; cur; cur = nxt[cur])
|
|
if (dis[to[cur]] > dis[que[h]] + len[cur])
|
|
{
|
|
dis[to[cur]] = dis[que[h]] + len[cur];
|
|
if (!inq[to[cur]])
|
|
que[t++] = to[cur], inq[to[cur]] = true;
|
|
}
|
|
}
|
|
void readint(int&x)
|
|
{
|
|
int ch=x=0;
|
|
while(!isdigit(ch=getchar()));
|
|
for(; isdigit(ch); ch=getchar())
|
|
x=x*10+ch-'0';
|
|
}
|
|
int main()
|
|
{
|
|
int T,n,m,ti,si;
|
|
readint(T);
|
|
for(int t=1; t<=T; t++)
|
|
{
|
|
ecnt=0;
|
|
memset(dis1,0x3f3f3f3f,sizeof(dis1));
|
|
memset(dis2,0x3f3f3f3f,sizeof(dis2));
|
|
memset(head,0,sizeof(head));
|
|
readint(n),readint(m);
|
|
for(int i=0,x; i<m; i++)
|
|
{
|
|
readint(ti),readint(si);
|
|
for(int j=0; j<si; j++)
|
|
readint(x),addEdge(x,n+10+i,ti),addEdge(n+10+i,x,ti);
|
|
|
|
/*for(int j=0; j<si; j++)
|
|
for(int k=0; k<j; k++)
|
|
addEdge(tmpe[j],tmpe[k],ti),addEdge(tmpe[k],tmpe[j],ti);*/
|
|
}
|
|
spfa(1,dis1),spfa(n,dis2);
|
|
/*for(int i=1; i<=n; i++)
|
|
printf("%.3d%c",dis1[i]," \n"[i==n]);
|
|
for(int i=1; i<=n; i++)
|
|
printf("%.3d%c",dis2[i]," \n"[i==n]);*/
|
|
map<ll,vector<int> >PP;
|
|
for(int j, i=2;i<n;++i)
|
|
if((j = max(dis1[i],dis2[i]))!=0x3f3f3f3f)
|
|
PP[j].push_back(i);
|
|
|
|
printf("Case #%d: ",t);
|
|
if(PP.empty())
|
|
puts("Evil John");
|
|
else
|
|
{
|
|
printf("%lld\n",PP.begin()->first/2);
|
|
for(int i=0;i<PP.begin()->second.size();++i)
|
|
printf("%d%c",PP.begin()->second[i]," \n"[i==PP.begin()->second.size()-1]);
|
|
}
|
|
}
|
|
return 0;
|
|
}
|