M.Meeting
题意给你n(n<=1e5)个点，m个关系：每个关系代表一个集合，包含权值v，表示该集合集合中两两的距离，还有集合的点的个数cnt和集合里的点的标号，相当于一个有距离的完全图。
保证集合中所有的点的数量不超过1e6。
两个人分别从1点和n点走，只可以在一个点相遇（一个人可以等另一个人），求最短相遇时间和最短时间的前提下在哪些编号的点相遇时间都是最短。
如果无法相遇，输出“Evil John”。
题解
就是求两个点的Dijkstra求最短路径，但是如何建图就很困难。因为一个完全图需要建n*(n-1)/2的边，容易超时，只能用组的方式建边。对于集合中每个点 建立一个虚拟的超级源点 下标记为(n+i) 比较常用的建图技巧
建边 该集合内任意一点x到n+i的距离为0,且n+i到该集合内任意一点距离为v。
这样保证集合中的任意两个点的距离是v。同时新建的图满足迪杰斯特拉算法的要求
可以直接跑最短路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
typedef pair<ll,ll> P;
const int mod=2e3;
const int maxn=2e5+5;
vector<P>mp[maxn];
ll dis[2][maxn];
bool vis[2][maxn];
void Djstar(int start,int typ){
dis[typ][start]=0;
priority_queue<P, vector<P>,greater<P> > Q;
Q.push(P(0,start));
while(!Q.empty()){
P x=Q.top();Q.pop();
int u=x.second;
if(vis[typ][u])continue;
vis[typ][u]=1;
for(auto i:mp[u]){
if(dis[typ][i.first]>dis[typ][u]+i.second){
dis[typ][i.first]=dis[typ][u]+i.second;
Q.push(P(dis[typ][i.first],i.first));
}
}
}
}
int main(){
Turnoff;
int t,cnt=1;cin>>t;
while(t--){
int n,m;cin>>n>>m;
for(int i=1;i<=2*n;i++){
mp[i].clear();
vis[0][i]=vis[1][i]=0;
dis[0][i]=dis[1][i]=1e18;
}
for(int i=1;i<=m;i++){
int d,num;cin>>d>>num;
for(int j=0;j<num;j++){
int indx;cin>>indx;
mp[indx].push_back({n+i,0});
mp[n+i].push_back({indx,d});
}
}
Djstar(1,0);Djstar(n,1);
ll minn=1e18;
for(int i=1;i<=n;i++){
minn=min(minn,max(dis[0][i],dis[1][i]));
}
cout<<"Case #"<<cnt++<<": ";
if(minn==1e18)cout<<"Evil John"<<endl;
else {
cout<<minn<<endl;bool flag=0;
for(int i=1;i<=n;i++){
if(max(dis[0][i],dis[1][i])==minn){
if(!flag)cout<<i;
else cout<<" "<<i;
flag=1;
}
}
cout<<endl;
}
}
}
|