HDU 6166 Senior Pan(2017 Multi-University Training Contest - Team 9)

HDU 6166 Senior Pan

题目大意:$n$ 个点$m$ 条边的有向图中,给定$k$ 个点,问这$k$ 个点两两间的最短路的最小值。

Dijkstra

因为题目要求的是两两不同点间的最短路,故可以将这k个点划分成两个集合,一个连接虚起点,另一个连接虚终点,求起点到终点的最短路即可。

如何划分?看到群里有人是用随机化划分过的,除了随机化还有一种靠谱的放法。

枚举二进制的每一位,将这$k$ 个数分成两个集合,这种做法保证了每两个点至少被分到两个集合一次。

复杂度$O(nlog^2n)$ 。

代码如下:

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
struct edge{
int t,w;
edge(int T,int W){t=T;w=W;}
};
struct node{
int v,d;
node(int V,int D){v=V;d=D;}
friend bool operator<(node a,node b){
return a.d>b.d;
}
};
const int N=100005;
const int inf=1e9;
vector<edge>e[N];
int vis[N],dis[N],adj[N][3];
priority_queue<node>q;
int dijkstra(int s,int t){
while(!q.empty())q.pop();
memset(vis,0,sizeof(vis));
for(int i=s;i<=t;++i)dis[i]=inf;
dis[s]=0;
q.push(node(s,0));
while(!q.empty()){
node t=q.top();q.pop();
int u=t.v;
if(vis[u])continue;
vis[u]=1;
for(int i=0;i<(int)e[u].size();++i){
int v=e[u][i].t,w=e[u][i].w;
dis[v]=min(dis[u]+w,dis[v]);
if(!vis[v])q.push(node(v,dis[v]));
}
}
return dis[t];
}
int T,n,m,k,a[N];
int main(void){
scanf("%d",&T);
for(int t=1;t<=T;++t){
int ans=inf;
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i)
for(int j=0;j<3;++j)
scanf("%d",&adj[i][j]);
scanf("%d",&k);
for(int i=0;i<k;++i)
scanf("%d",&a[i]);
for(int i=0;i<20;++i){
for(int op=0;op<2;++op){
for(int j=0;j<=n+1;++j)e[j].clear();
for(int j=0;j<m;++j)e[adj[j][0]].push_back(edge(adj[j][1],adj[j][2]));
for(int j=0;j<k;++j){
if(((a[j]>>i)&1)==op)e[0].push_back(edge(a[j],0));
else e[a[j]].push_back(edge(n+1,0));
}
ans=min(ans,dijkstra(0,n+1));
}
}
printf("Case #%d: %d\n",t,ans);
}
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×