HDU5521 Meeting
题意：
给你n个点，它们组成了m个团，第i个团内有si个点，且每个团内的点互相之间距离为ti，问如果同时从点1和点n出发，最短耗时多少相遇
很明显题目给出的是个无负环的图，且要跑出单源最短路，那不就是个dij吗
大方向定下，但图该怎么建呢？
way1:
给每个团内的所有点两两暴力建边
如图所示：黑的为点，红的为团，相同颜色的边长度相等
共 (sum ^{m}_{i=1}dfrac {1}{2}s_{i}left( s_{i}-1 ight)) 条边
而题面又告诉我们 (sum ^{m}_{i=1}s_{i}<=10^6)
边数1e12这谁顶得住啊QuQ
way2:
我们再看上面这张图，发现同个团内类似三角形的东西其实是不需要的，因为反正有更近的直接连接的边，为啥还要再去绕个圈去松弛操作呢？
这时候我们就可以在每个团中建个虚点，改无向图为有向图，即实点可以0消耗到虚点，虚点要ti到实点
正如下图所示：
蓝色的为虚点，灰色的为从实点到虚点的路径，长度为0；彩色的为从虚点到实点的路径，长度为ti
边数是不是被减少到了 (sum ^{m}_{i=1}2s_{i}) ？是不是很优秀？
建完图后，分别以1和n为起点，跑一遍最短路
(Ans=min{max{点1到点i最短路,点n到点i最短路|1<=i<=n}})
ps.这道题十分毒瘤，我提交后曾四次PE，输出请注意你的空格以及换行，避免冗余
typedef long long ll;
const int N=2e5+5,M=4e6+5;
int en,T,n,m,h[N],cnt,ans[N],nm;
ll dis[2][N];
struct node{
int x; ll v;
inline bool operator < (const node &nt) const {return v>nt.v;}
};
struct edge{int n,v;ll w;}e[M]; //前向星存边
inline void add(const int &x,const int &y,const ll &z){e[++en]=(edge){h[x],y,z};h[x]=en;}
void dij(int s){ //一个堆优dijkstra模板
int pos; //小技巧，提前判断好当前最短路应存进哪个dis[]数组
if(s==1) pos=0;
else pos=1;
priority_queue<node> q;
memset(dis[pos],66,sizeof dis[pos]);
q.push((node){s,0});
dis[pos][s]=0;
while(!q.empty()){
node x=q.top();
q.pop();
if(x.v!=dis[pos][x.x]) continue;
for(int i=h[x.x];i;i=e[i].n){
int y=e[i].v;
if(dis[pos][x.x]+e[i].w<dis[pos][y]){
dis[pos][y]=dis[pos][x.x]+e[i].w;
q.push((node){y,dis[pos][y]});
}
}
}
}
signed main(){
scanf("%d",&T);
while(T--){
en=nm=0;
memset(h,0,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1,t,s;i<=m;i++){
scanf("%d%d",&t,&s);
int center=n+i; //虚点
for(int i=1,x;i<=s;i++){
scanf("%d",&x);
add(x,center,0); //实点到虚点无长度
add(center,x,t); //虚点到实点有长度
}
}
dij(1); //从1跑
dij(n); //从n跑
ll MIN=dis[0][0];
for(int i=1;i<=n;i++){
ll tp=max(dis[0][i],dis[1][i]);
if(tp==MIN)
ans[++nm]=i; //nm记录当前最优解共有几个，ans[]记录这些满足最优解的下标
if(tp<MIN){
nm=1; //比当前最优解还优，刷新，重新从1开始
ans[1]=i;
MIN=tp;
}
}
printf("Case #%d: ",++cnt);
if(MIN==dis[0][0]) printf("Evil John
"); //没有最优解->即无解
else{
printf("%lld
",MIN);
for(int i=1;i<=nm;i++)
if(i<nm)
printf("%d ",ans[i]);
else
printf("%d
",ans[i]); //最后一个后无空格
}
}
}