题目描述
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 n blocks. Bessie lives in the 1st block while Elsie lives in the n-th one. They have a map of the farm which shows that it takes they ti minutes to travel from a block in Ei to another block in Ei where Ei 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.
输入
The first line contains an integer T (1 ≤ T ≤ 6), the number of test cases.
Then T test cases follow.
The first line of input contains n and m. 2 ≤ n ≤ 105 . The following m lines describe Ei (1 ≤ Ei ≤ 109 ). Each line will contain two integers ti and Si firstly. Then Si integer follows and the blocks numbered of these integers forms the set Ei . It is guaranteed that
输出
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.
样例输入
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
样例输出
Case #1: 3
3 4
Case #2: Evil John
提示
In the first case, it will take Bessie 1 minutes to travel to the 3rd block, and it will take Elsie 3 minutes to travel to the 3rd block. It will take Bessie 3 minutes to travel to the 4th block, and it will take Elsie 3 minutes to travel to the 4th block.
In the second case, it is impossible for them to meet.
题意： 有两个人分别在节点1和节点n，现在给出m个集合，每个集合内任意两个节点的移动时间为Ti，现在两人同时出发，问在哪些节点相遇，用的时间最少，升序输出这些结点标号。如果不能相遇输出Evil John。
题解： 首先可以知道，要最小时间相遇，并且已经有了节点之间行走的时间，大概就是一个最短路的模型，可以根据集合信息，表示集合内任意两点是相连的。边权即每个集合的Ti，从起点求一个最短路，再从终点求一个最短路，遍历所有节点，对于每个节点，拿从起点到该节点和从终点到该节点的最短路进行比较，较大花费的作为两人在此花费的时间【因为先到的人花费虽然小，但是得等花费更多的人到了才能碰面，因此两者总花费是较大的那个人的】，求出所有节点相遇的时间后，取最小值作为答案，然后对比所有花费时间等于答案的节点，升序输出即可。
但是！
在建图的第一步就遇到了困难，因为不是正常的给一条边的两端点就建边，而是个一个集合，集合内所有节点两两建边，这样的边数就是n^2级别的，如果一个集合特别大，边数将会爆炸。
我们注意到，通过集合建边，有些节点因为同时处于不同的集合，或是说被多个集合所囊括，因此我们能做到集合间的移动，这样才能使两人相遇，很明显，当两人位置本身就在一个集合中时，无需计算，直接就是Ti为最小花费，因为起点和终点相连，这就是最小花费，当两者不在同一集合时，就需要通过一些被多个集合覆盖的节点进行跨集合的移动。
如上所示。
我们要考虑一种建图方式，使得能够方便的进行集合间的移动，并且集合内也不能暴力的进行任意两点的N^2建图。
一种方式是，对于一个集合，我们新建立一个虚点，这个虚点连向该集合内所有的点。这样集合内任意两点的连同就通过这个虚点实现，建立虚点的方法能有效减少过多的边数，将N^2条边变成2*N条边。关于边权，全部建立有向边，集合内每个节点向指向虚点，边权为Ti，虚点指向所有节点建立有向边，边权为0，边权反过来也可以，这样就实现了集合内简化边数且节点联通。
在每个集合内这样建边，于是，跨域集合间的边将同时被多个虚点所接受。
这样就实现了避免集合内过多边，且让集合间相互沟通的方式建图。在这个新图上跑两遍最短路即可。
#include<bits/stdc++.h>
#define LL long long
#define M(a,b) memset(a,b,sizeof a)
#define pb(x) push_back(x)
using namespace std;
const int maxn=1000008;
const LL inf=1LL<<60;
struct edge
{
int nxt,to;
LL val;
edge() {}
edge(int a,LL b,int c)
{
to=a,val=b,nxt=c;
}
} mp[maxn<<1];
int head[maxn],cnt;
struct node
{
int to;
LL val;
node(int a,LL b)
{
to=a,val=b;
}
bool operator <(const node &a)const
{
return val>a.val;
}
};
void addedge(int from,int to,LL val)
{
mp[cnt]=edge(to,val,head[from]);
head[from]=cnt++;
mp[cnt]=edge(from,0,head[to]);
head[to]=cnt++;
}
int n,m;
void dijkstra(int st,LL dist[])
{
bool vis[maxn];
for(int i=1; i<=n+m; i++)vis[i]=false,dist[i]=inf;
dist[st]=0;
priority_queue<node>q;
q.push(node(st,0));
while(!q.empty())
{
node tp=q.top();
q.pop();
if(vis[tp.to])continue;
vis[tp.to]=true;
for(int i=head[tp.to];i!=-1; i=mp[i].nxt)
{
edge tmp=mp[i];
if(dist[tmp.to]>tp.val+tmp.val)
{
dist[tmp.to]=tp.val+tmp.val;
q.push(node(tmp.to,dist[tmp.to]));
}
}
}
}
LL dist1[maxn],dist2[maxn];
int main()
{
int t,x,cas=0;
scanf("%d",&t);
while(t--)
{
cas++;
M(head,-1);
cnt=0;
LL ti;
int si;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
scanf("%lld%d",&ti,&si);
for(int j=1; j<=si; j++)
{
scanf("%d",&x);
addedge(x,n+i,ti);
}
}
dijkstra(1,dist1);
if(dist1[n]==inf)
{
printf("Case #%d: Evil John
",cas);
continue;
}
dijkstra(n,dist2);
LL mi=inf;
for(int i=1; i<=n; i++)
{
LL tmp=max(dist1[i],dist2[i]);
if(tmp<mi)mi=tmp;
}
printf("Case #%d: %lld
",cas,mi);
bool flag=false;
for(int i=1; i<=n; i++)
{
LL tmp=max(dist1[i],dist2[i]);
if(tmp==mi)
{
if(!flag)printf("%d",i),flag=true;
else printf(" %d",i);
}
}
puts("");
}
}