(未完待续)$\texttt{Dijkstra}$ 好题。
题目链接:Luogu P5304/LibreOJ 3087/BZOJ 5506/GXOI&GZOI2019 D2T2。
题目
题目描述
J 国有 $n$ 座城市,这些城市之间通过 $m$ 条单向道路相连,已知每条道路的长度。
一次,居住在 J 国的 Rainbow 邀请 Vani 来作客。不过,作为一名资深的旅行者,Vani 只对 J 国的 $k$ 座历史悠久、自然风景独特的城市感兴趣。
为了提升旅行的体验,Vani 想要知道他感兴趣的城市之间「两两最短路」的最小值(即在他感兴趣的城市中,最近的一对的最短距离)。
也许下面的剧情你已经猜到了——Vani 这几天还要忙着去其他地方游山玩水,就请你帮他解决这个问题吧。
多组数据,数据组数为 $T$。
数据范围
变量 | 数据范围 |
---|---|
数据组数 | $\leq 5$ |
$n$ | $\leq 10^5$ |
$m$ | $\leq 5\times 10^5$ |
$k$ | $\leq n$ |
边权 | $\leq 2\times 10^9$ |
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
Luogu P5304 | $5\text{s}$ | $500\text{MiB}$ |
LibreOJ 3087 | $5\text{s}$ | $512\text{MiB}$ |
BZOJ 5506 | $50\text{s}$ | $512\text{MiB}$ |
GXOI&GZOI2019 D2T2 | $5\text{s}$ | $512\text{MiB}$ |
题解
解法 A
其实是官方题解。
思路
假设答案是 $(a,b)$ 之间的最短路($a,b$ 指在 $k$ 个数中的序号,不是节点编号),那么显然有 $a\ne b$,进一步地,$a$ 与 $b$ 间至少有 $1$ 个二进制位不同。
考虑枚举每一个二进制位 $t$,$t$ 这位为 $1$ 的算作集合 $A$,为 $0$ 的记作集合 $B$,集合 $A$ 向 $s$ 连一条零权边,集合 $B$ 向 $t$ 连一条零权边,求 $s$ 到 $t$ 的最短路,那么我们可以知道,答案一定在这些最短路中,找到最小的就是了。
代码
略。
解法 B
思路
最短路 + 染色。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll; //这道题要开 long long
#define INF 0X3F3F3F3F3F3F3F3F //正无穷
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXN=100000+5;
const int MAXM=500000+5;
const int MAXK=MAXN;
int n,m,K;
int id[MAXK];
int cnt,head[MAXN],to[MAXM],Next[MAXM];
ll w[MAXM];
inline void Add_Edge(reg int u,reg int v,reg ll len){
Next[++cnt]=head[u];
to[cnt]=v;
w[cnt]=len;
head[u]=cnt;
return;
}
struct Node{ //Dijkstra 存储用的结构体
int id;
ll dis;
inline Node(reg int id=0,reg ll dis=0):id(id),dis(dis){
return;
}
inline bool operator<(const Node& a)const{
return dis<a.dis;
}
inline bool operator>(const Node& a)const{
return dis>a.dis;
}
};
bool vis[MAXN];
priority_queue<Node,vector<Node>,greater<Node>/**/> Q; //优先队列
inline void Dijkstra(reg ll *dis,reg int *color){ //参数是两个数组,一个是 dis[] 距离,一个是 color[] 颜色
memset(vis,false,sizeof(vis));
for(reg int i=1;i<=n;++i)dis[i]=INF; //初始化距离
while(!Q.empty())Q.pop();
for(reg int i=1;i<=K;++i){ //K 个起点
dis[id[i]]=0;
color[id[i]]=id[i]; //染色
Q.push(Node(id[i],0));
}
while(!Q.empty()){
reg int ID=Q.top().id;
Q.pop();
if(vis[ID])
continue;
vis[ID]=true;
for(reg int i=head[ID];i;i=Next[i])
if(dis[to[i]]>dis[ID]+w[i]){
dis[to[i]]=dis[ID]+w[i];
color[to[i]]=color[ID]; //染色
Q.push(Node(to[i],dis[to[i]]));
}
}
return;
}
int X[MAXM],Y[MAXM],W[MAXM];
ll dis[2][MAXN];
int c[2][MAXN];
inline void Init(void){ //初始化
cnt=0;
memset(head,0,sizeof(head));
return;
}
inline void Solve(void){
n=read(),m=read(),K=read();
for(reg int i=1;i<=m;++i)
X[i]=read(),Y[i]=read(),W[i]=read();
for(reg int i=1;i<=K;++i)
id[i]=read();
Init(); //别忘了初始化
for(reg int i=1;i<=m;++i)
if(X[i]!=Y[i])
Add_Edge(X[i],Y[i],W[i]);
Dijkstra(dis[0],c[0]);
Init(); //别忘了初始化
for(reg int i=1;i<=m;++i)
if(X[i]!=Y[i])
Add_Edge(Y[i],X[i],W[i]);
Dijkstra(dis[1],c[1]);
ll ans=INF;
for(reg int i=1;i<=m;++i){ //求结果
reg int x=X[i],y=Y[i],w=W[i];
if(c[0][x]&&c[1][y]&&c[0][x]!=c[1][y])
ans=min(ans,dis[0][x]+dis[1][y]+w);
}
printf("%lld\n",ans); //输出答案
return;
}
int main(void){
reg int T=read();
while(T--)
Solve(); //多组数据
return 0;
}
近期评论