题意
A,B两个人分别在1和n区。每个区有若干点（区之间的点可以重复，各个区内点间的距离一致），给出区之间有联系的图以及到达所需时间。求两个人见面最短时间以及在哪个区碰面（可有多个）
分析
隐式图搜索。但是注意一点：当我们搜索过一个区之后，这个区的最短路一定是被更新完成的，最短的（只要没有负权边）。因此，我们应当对已经访问过的点加一个标记，即可极大的剪枝，加快对隐式图的Dijkstra。
另一种做法
对于每个区定义一个新的虚拟点，区中的每个点到这点的距离是给定的\(t_i\)（不去生成一个完全图）。这样求最短路后距离除以二即可。
这样的做法可能在网络流中会比较有用，值得注意。
代码
注意行末空格，会让你丢一次PE。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <unordered_map>
#include <queue>
#define rep(i,a,b) for(repType i=(a);i<=(b);++i)
#define per(i,a,b) for(repType i=(a);i>=(b);--i)
#define fi first
#define ZERO(x) memset(x,0,sizeof(x))
#define se second
#define PB emplace_back
#define MP make_pair
using namespace std;
typedef long long ll;
typedef int repType;
const int MAXN=2e5+5;
vector<int> ma[1000005];
vector<int> gra[MAXN];
ll cost[1000005];
ll dist[MAXN];
ll distb[MAXN],mindist,inf;
bool vis[1000005];
void dijkstra(int b, int n)
{
ZERO(vis);
memset(dist,0x3f,sizeof(dist));
inf=dist[0];
dist[b]=0;
typedef pair<ll,int> P;
priority_queue<P, vector<P>, greater<P> > pq;
pq.push(MP(0,b));
while(!pq.empty())
{
P now=pq.top();
pq.pop();
if(dist[now.se]<now.fi) continue;
/*
printf("Point %d belongs to set: ", now.se);
rep(i, 0, int(ma[now.se].size())-1)
{
cout<<ma[now.se][i]<<" ";
}
cout<<endl;
*/
rep(i, 0, int(ma[now.se].size())-1) //分别属于哪些集合
{
if(!vis[ma[now.se][i]]) // Important here!
vis[ma[now.se][i]]=true;
else continue;
/*
printf(" Set %d has pnts:", ma[now.se][i]);
rep(j,0,int(gra[ma[now.se][i]].size())-1)
printf("%d ",gra[ma[now.se][i]][j]);
cout<<endl;
*/
rep(j, 0, int(gra[ma[now.se][i]].size())-1) //集合分别有哪些点
{
int v=gra[ma[now.se][i]][j];
ll w=cost[ma[now.se][i]]; // 点是啥
if(dist[v]>dist[now.se]+w)
{
dist[v]=dist[now.se]+w;
//pre[now.se]=ma[now.se][i];
pq.push(MP(dist[v],v));
}
}
}
}
}
int main()
{
int T; scanf("%d",&T);
rep(kase, 1, T)
{
int n,m; scanf("%d%d", &n,&m);
rep(i,1,n) ma[i].clear();
rep(i,1,m) gra[i].clear();
rep(i,1,m)
{
int s; scanf("%lld%d", &cost[i], &s);
rep(j,1,s)
{
int tmp; scanf("%d",&tmp);
ma[tmp].PB(i); // 元素分别属于第几块
gra[i].PB(tmp); // 第几块 哪些元素
}
}
dijkstra(1,n);
memcpy(distb,dist,sizeof(dist));
dijkstra(n,n);
mindist=inf;
vector<int> pnt;
rep(i,1,n)
{
ll tmp=max(distb[i],dist[i]);
if(tmp==inf) continue;
if(tmp<mindist)
{
mindist=tmp;
pnt.clear(); pnt.PB(i);
}
else if(tmp==mindist)
{
pnt.PB(i);
}
}
printf("Case #%d: ",kase);
if(pnt.size()==0)
{
printf("Evil John\n");
}
else
{
printf("%lld\n",mindist);
rep(i,0,int(pnt.size())-1)
{
printf("%d",pnt[i]);
printf("%s",i==int(pnt.size())-1?"\n":" ");
}
}
}
return 0;
}