[hdoj5521]Meeting

Meeting

题意

将图分成$m$个块,每个块中的点到块中点的需要的时间为$E_i$。Bessie在点1,Elsie在点$n$,问他们在最短的时间走到可以到哪一个点会和。点可以在不同的块中。

题解

如果想要每个点都建边,无疑会爆空间。我们可以看出每个点都分配到几个块,而每个块又有几个点。那么我们可以将块看做点,连接着块中的点,这样每个块的边从$O(n^2)$变成了$O(n)$。


我tmWA了20发,就是因为以前都是将点做标记,但是这次是块也要做标记,不然每块会浪费很多时间。而且因为只要该点是最优的,那么该块也是最优的了(因为该点到该块的距离为0)。

AC代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define pb push_back
const int maxn = 1e5 + 10;
ll val[maxn];
ll cnt1[maxn],cnt2[maxn];
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//head
int T,n,m;
ll ans[maxn];
int vis[maxn];
struct node{
ll t;
int id;
node(){}
node(ll a,int b):t(a),id(b){}
bool operator<(const node&x) const{
return t > x.t;
}
};
void bfs(int rt,ll *cnt,vector<int>B[],vector<int>E[]){
cnt[rt] = 0;
priority_queue<node > q;
memset(vis,0,sizeof(vis));
int use[maxn];
memset(use,0,sizeof(use));
q.push(node(0,rt));
while(!q.empty()){
int u = q.top().id; q.pop();
for(auto bk:B[u]){
if(use[bk]) continue;
use[bk] = 1;
for(auto v: E[bk]){
if(cnt[u]+val[bk]>=cnt[v]) continue;
cnt[v] = cnt[u] + val[bk];
q.push(node(cnt[v],v));
}
}
}
}
int main(){
#ifdef LOCAL
freopen("m.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
memset(cnt1,127,sizeof(cnt1));
memset(cnt2,127,sizeof(cnt2));
scanf("%d%d",&n,&m);
vector<int> B[n+1];
vector<int> E[m+1];
rep(i,1,n+1) B[i].resize(5);
rep(i,1,m+1) E[i].resize(5);
rep(i,1,m+1){
val[i] = read(); int s = read();
rep(j,0,s){
int x = read();
E[i].pb(x);B[x].pb(i);
}
}
bfs(1,cnt1,B,E); bfs(n,cnt2,B,E);
ll mmin = 0xfffffff;
rep(i,1,n+1){
ans[i] = max(cnt1[i],cnt2[i]);
if(ans[i]<mmin) mmin=ans[i];
}
if(mmin != 0xfffffff)
printf("Case #%d: %lld\n",test_case,mmin);
else{
printf("Case #%d: Evil John\n",test_case);
continue;
}
int cnt = 0;
ll res[maxn];
rep(i,1,n+1){
if(ans[i]==mmin)
res[cnt++] = i;
}
rep(i,0,cnt){
printf("%d%c",res[i],i==cnt-1?'\n':' ');
}
}
}