Meeting
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 3533 Accepted Submission(s): 1136
Problem Description
Bessie and her friend Elsie decide to have a meeting. However, after Farmer John decorated his
fences they were separated into different blocks. John's farm are divided into blocks labelled from to .
Bessie lives in the first block while Elsie lives in the -th one. They have a map of the farm
which shows that it takes they minutes to travel from a block in to another block
in where is a set of blocks. They want to know how soon they can meet each other
and which block should be chosen to have the meeting.
Input
The first line contains an integer , the number of test cases. Then test cases
follow.
The first line of input contains and . . The following lines describe the sets . Each line will contain two integers and firstly. Then integer follows which are the labels of blocks in . It is guaranteed that .
Output
For each test case, if they cannot have the meeting, then output "Evil John" (without quotes) in one line.
Otherwise, output two lines. The first line contains an integer, the time it takes for they to meet.
The second line contains the numbers of blocks where they meet. If there are multiple
optional blocks, output all of them in ascending order.
Sample Input
2
5 4
1 3 1 2 3
2 2 3 4
10 2 1 5
3 3 3 4 5
3 1
1 2 1 2
Sample Output
Case #1: 3
3 4
Case #2: Evil John
Hint
In the first case, it will take Bessie 1 minute travelling to the 3rd block, and it will take Elsie 3 minutes travelling to the 3rd block. It will take Bessie 3 minutes travelling to the 4th block, and it will take Elsie 3 minutes travelling to the 4th block. In the second case, it is impossible for them to meet.
Source
2015ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）
【题意】：
有n个点，和m个集合。
每个集合里有一些点，这些点之间的距离全部为输入的ti值。
然后两个人从1和n分别出发，去任意一个点上见面，使得距离最短（题目中描述的time可以看做距离）
【体会】：
必须要说一下这个题收获颇深！
拿到题目后心里很明白，只要把图建成，跑两边最短路即可。可是图示以集合的形式给出的；
难就难在建图。
最初我是直接集合内部两两链接建图，但是边太多了！超时超内存打不了。
后来我直接不建图了，用spfa跑这个集合。
具体方法见分析。
之后去看百度的题解，哇，真是太巧妙了，还有这种建图操作。
总之是干出颇深，长见识了。
【分析】：
方法1：
用链式前向星存两个关系。
e存 点u的所在集合编号。
e2存集合i的所有元素。
跑spfa，在这两个关系上。
用len[]表示跑到集合i的最短距离。
用dis[]表示跑到点i的最短距离。
优先判断len[],如果len[]得到了更新，那么再去更新这个集合内的点的距离dis。
这种操作也是第一次尝试。
别忘了加优化inq[]，标记点入队列,同一个点无需入多次队列
方法2：
看到网上的题解，这建图方法佩服。
对于每一个集合，虚拟出一个点来，让集合内所有点链接它（试着画画图）。
这些集合一定有交集，否则图不通。
然后跑n+m个点的最短路。但是每个点要先走到虚拟点，才能再走到其他点，所以跑最短路，最后再除以2，才是真实的最短路。
跑完最短路，下面的操作就水了，不啰嗦了。
【代码（方法1）】：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF=1ll<<32;
const int MAX=1e6+5;
struct node{
int t;
int next;
}e[MAX*6],e2[MAX*6];
int head[100110],cnt;
void add(int u,int se)//u的所在集合se
{
e[cnt].t=se;
e[cnt].next=head[u];
head[u]=cnt++;
}
int ti[MAX],cn;//第i个集合的元素
void add2(int i,int E)//第i个集合内的元素E
{
e2[cn].t=E;
e2[cn].next=ti[i];
ti[i]=cn++;
}
int T,n,m,s,u;
ll dis1[100110],disn[100110];
int t[MAX];//第i个集合的时间
ll len[MAX];
void spfa(int s,ll dis[])
{
for(int i=0;i<=n;i++)dis[i]=INF;
for(int i=0;i<=m;i++)len[i]=INF;
dis[s]=0;
queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop(); //现在u为起点
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].t;//u在第v个集合
if(len[v]>dis[u]+t[v])//到达集合v中的点的距离
{
len[v]=dis[u]+t[v];
for(int k=ti[v];~k;k=e2[k].next)//跑第v个集合
if(dis[e2[k].t]>len[v])
{
dis[e2[k].t]=len[v];
q.push(e2[k].t);
}
}
}
}
}
int main()
{
scanf("%d",&T);
for(int h=1;h<=T;h++)
{
scanf("%d%d",&n,&m);
cn=cnt=0;
for(int i=0;i<=n;i++)ti[i]=head[i]=-1;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&t[i],&s);
while(s--)
{
scanf("%d",&u);
add(u,i);//u在第i个集合中
add2(i,u);//第i个集合中有u
}
}
spfa(1,dis1);
spfa(n,disn);
ll flag=INF;
for(int i=1;i<=n;i++)
{
dis1[i]=max(dis1[i],disn[i]);
flag=min(flag,dis1[i]);
}
if(flag==INF){
printf("Case #%d: Evil John\n",h);
continue;
}
printf("Case #%d: %d\n",h,flag);
int ans[100100],top=0;
for(int i=1;i<=n;i++)
if(dis1[i]==flag)
ans[top++]=i;
for(int i=0;i<top-1;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[top-1]);
}
return 0;
}【代码（方法2）】：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF=1ll<<45;
const int MAX=1e6+5;
struct node{
int t,time;
int next;
}e[MAX*2];
int head[MAX<<1],cnt;
void add(int u,int v,int time)
{
e[cnt]=node{v,time,head[u]};
head[u]=cnt++;
}
int T,n,m,time,s,u;
ll dis1[MAX<<1],disn[MAX<<1];
bool inq[MAX<<1];
void spfa(int s,ll dis[])
{
for(int i=0;i<=n+m;i++)dis[i]=INF<<1;
memset(inq,0,sizeof(inq));
dis[s]=0;
queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
inq[u]=0;
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].t;
if(dis[v]>dis[u]+e[i].time)
{
dis[v]=dis[u]+e[i].time;
if(!inq[v])
{
inq[v]=1;
q.push(v);
}
}
}
}
}
int main()
{
scanf("%d",&T);
for(int h=1;h<=T;h++)
{
scanf("%d%d",&n,&m);
cnt=0;
for(int i=0;i<=n+m;i++)head[i]=-1;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&time,&s);
while(s--)
{
scanf("%d",&u);
add(u,i+n,time);
add(i+n,u,time);
}
}
spfa(1,dis1);
spfa(n,disn);
ll flag=INF;
for(int i=1;i<=n;i++)
{
dis1[i]=max(dis1[i]/2,disn[i]/2);
flag=min(flag,dis1[i]);
}
if(flag==INF){
printf("Case #%d: Evil John\n",h);
continue;
}
printf("Case #%d: %d\n",h,flag);
int ans[100100],top=0;
for(int i=1;i<=n;i++)
if(dis1[i]==flag)
ans[top++]=i;
for(int i=0;i<top-1;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[top-1]);
}
return 0;
}