题意：
给你n个点，然后有m个城市群，城市群之间相互可以在ti时间内到达，现在问两个人从1和n同时出发，最少需要花费多少时间相遇，然后输出可能的相遇地点。
思路：
首先是间城市群转化为有向图，每个城市群增加一个点，从每个城市有一条出边和一条入边，权值是ti/2（实际代码实现的时候为了避免浮点数，都乘了2），然后这个用少量的边就满足了题目的城市群互达的条件了。 然后就从1和n做一遍单源最短路就好了，对它们到达某个点的时间a[i]和b[i]取最大值，这个值就是两人在这里相遇所需要的时间，然后找个最小的就是答案了，再把方案输出就好了。 写的时候数组的大小名写错了，wa了一发，好像这种错误不是一次两次了，警记交之前看一遍
代码：
#define debug printf
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int maxn=
1e5+
100;
const int maxm=
3e6+
100;
int T;
int n,m;
int kase=
0;
struct Edge{
int v,w,next;
Edge(){}
Edge(
int v,
int w,
int next)
:v(v),w(w),next(next){}
};
const int maxnode=
1e6+maxn;
Edge edges[maxm];
int head[maxnode];
int edgescnt;
LL times[maxnode],timed[maxnode];
bool viss[maxnode],visd[maxnode];
const LL INF=
1e18;
void initEdge();
void AddEdge(
int u,
int v,
int w);
void Dijkstra(
int s,LL * d,
int n,
bool done[]);
void solve();
int main()
{
scanf(
"%d",&T);
kase=
0;
while(T--){
kase++;
solve();
}
return 0;
}
void initEdge()
{
memset(head,-
1,
sizeof(head));
edgescnt=
0;
}
void AddEdge(
int u,
int v,
int w)
{
edges[edgescnt]=Edge(v,w,head[u]);
head[u]=edgescnt++;
}
void solve()
{
scanf(
"%d %d",&n,&m);
initEdge();
int time,sz,u;
for(
int i=
1;i<=m;i++){
scanf(
"%d %d",&time,&sz);
for(
int j=
1;j<=sz;j++){
scanf(
"%d",&u);
AddEdge(u,i+n,time);
AddEdge(i+n,u,time);
}
}
Dijkstra(
1,times,n+m,viss);
Dijkstra(n,timed,n+m,visd);
LL ans=INF;
LL tmpmin=INF;
for(
int i=
1;i<=n;i++){
tmpmin=max(times[i],timed[i]);
if(tmpmin<ans){
ans=tmpmin;
}
}
if(ans==INF){
printf(
"Case #%d: Evil John\n",kase);
return;
}
vector<int> res;
for(
int i=
1;i<=n;i++){
tmpmin=max(times[i],timed[i]);
if(tmpmin==ans){
res.push_back(i);
}
}
printf(
"Case #%d: %lld\n",kase,ans/
2);
for(
int i=
0;i<res.size();i++){
if(i!=
0)
printf(
" ");
printf(
"%d",res[i]);
}
printf(
"\n");
}
struct HeapNode{
LL d;
int u;
HeapNode(){}
HeapNode(LL d,
int u)
:d(d),u(u){}
bool operator < (
const HeapNode & rhs)
const
{
return d>rhs.d;
}
};
void Dijkstra(
int s,LL * d,
int n,
bool done[])
{
priority_queue<HeapNode> Q;
for(
int i=
1;i<=n;i++) d[i]=INF;
d[s]=
0;
for(
int i=
1;i<=n;i++) done[i]=
false;
Q.push(HeapNode(
0,s));
while(!Q.empty()){
HeapNode x=Q.top();Q.pop();
int u=x.u;
if(done[u])
continue;
done[u]=
true;
for(
int e=head[u];e!=-
1;e=edges[e].next){
int v=edges[e].v,w=edges[e].w;
if(d[v]>d[u]+LL(w)){
d[v]=d[u]+LL(w);
Q.push(HeapNode(d[v],v));
}
}
}
}
