思路：
看了好久才看懂题意，文中给了n个点，有m个集合，每个集合有s个点，集合内的每两个点之间有一个权值为t的边，现在有两个人，要从1号点，和n号点，走到同一个顶点，问最少花费以及花费最少的点。
那就直接跑两遍最短路，然后枚举每一点，取最短路最大值最小的点。
然而这么浅显的做法却MLE啦，真是用心险恶的出题人呀。
其实仔细想一想就知道了，题目的要求是，每个集合里面，都是一个完全图，如果只有一个集合，那么2e5个点，边的条数就是4e10条，爆内存简直是必然的。所以需要在建图的时候优化，或者是换一种算法。如果要在建图的时候优化，那么就要忽视那些，在集合内，却没有与其他集合相连的点。如何找出这些点呢？很容易想到，如果一个点在输入的数据中出现了两次或以上，那么它一定是与其他集合有关的，但是如何记录这些点是一个很大的问题。如果用数组记录下每个集合有哪些点，或者每个点属于哪些集合，很明显都是不行的，但是如果使用vector呢？既然题目中已经提到了，s的和不会超过1e6，那么这样或许是可行的。我首先尝试了一下，记录下每个集合有哪些点。
然而还是炸了内存。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
自闭。
回来再想一想，好像还是没有最开始的完全图问题，因为这数据可以有两个集合，而这两个集合都是满的。。。。。（好歹毒呀）
最后我还是无耻得看了一下其他人的题解.了解了一种可以大幅减少完全图的边数.方法就是,在每一个完全图的边上,建一个虚拟点,让每一点去虚拟点的距离就是t,回来是0.如果是一般情况,也就是说,点到点之间的距离不相等的话,这个方法貌似就无法使用啦.
代码:
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 1.0e9+;
const ll INF = ;
const double eps = 1e-; int n,m;
ll diss1[maxn],diss2[maxn];
int num[maxn];
vector<int>u[maxn];
vector<ll>w[maxn];
bool book[*maxn];
void init()
{
for(int i=;i<=n*;i++){
u[i].clear();
w[i].clear();
diss1[i]=diss2[i]=INF;
}
} struct node
{
int x;
ll s;
bool operator<(const node p)const{return p.s<s;}
};
int Dijkstra(int sx,ll *dis)
{
memset(book,,sizeof(book));
dis[sx]=0ll;
priority_queue<node>q;
node exa;
exa.x=sx;
exa.s=0ll;
q.push(exa);
while(!q.empty()){
exa=q.top();q.pop();
if(book[exa.x]){continue;}
book[exa.x]=true;
int t=exa.x;
int siz=u[t].size();
for(int i=;i<siz;i++){
if(dis[u[t][i]]>dis[t]+w[t][i]){
dis[u[t][i]]=dis[t]+w[t][i];
exa.s=dis[u[t][i]];
exa.x=u[t][i];
q.push(exa);
}
}
}
} int main()
{
// ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin); int T;
scanf("%d",&T);
int cases = ;
while(T--){
cases++;
scanf("%d%d",&n,&m);
init();
for(int i=;i<=m;i++){
int ss;
ll t;
scanf("%lld%d",&t,&ss);
for(int j=;j<=ss;j++){
scanf("%d",&num[j]);
}
for(int j=;j<=ss;j++){
u[num[j]].push_back(n+i);
w[num[j]].push_back(t);
u[n+i].push_back(num[j]);
w[n+i].push_back();
}
} Dijkstra(,diss1);
Dijkstra(n,diss2); ll ans = INF;
for(int i=;i<=n;i++){
diss1[i]=max(diss1[i],diss2[i]);
ans=min(ans,diss1[i]);
} printf("Case #%d: ",cases);
if(ans ==INF){printf("Evil John\n");continue;}
else printf("%lld\n",ans);
vector<int>anss;
for(int i=;i<=n;i++){
if(ans==diss1[i]){anss.push_back(i);}
}
int siz = anss.size();
for(int i=;i<siz-;i++){
printf("%d ",anss[i]);
}
printf("%d\n",anss[siz-]);
} return ;
}
∑mi=1Si≤10