传送门
problem
J 国有
n
n
n 座城市，这些城市之间通过
m
m
m 条单向道路相连，已知每条道路的长度。
一次，居住在 J 国的 Rainbow 邀请 Vani 来作客。不过，作为一名资深的旅行者，Vani 只对 J 国的
k
k
k 座历史悠久、自然风景独特的城市感兴趣。
请求出 Vani 感兴趣的城市之间「两两最短路」的最小值（即在他感兴趣的城市中，最近的一对的最短距离）。
数据范围：
n
≤
1
0
5
n≤10^5
n≤105，
m
≤
5
×
1
0
5
m≤5\times 10^5
m≤5×105，
2
≤
k
≤
n
2\le k\le n
2≤k≤n。
solution
这道题其实不难。
我们跑两次 dijkstra，第一次从所有关键点出发，每个点记录两个值：
d
i
s
1
[
i
]
dis_1[i]
dis1[i] 为
i
i
i 到最近的关键点的距离，
p
r
e
1
[
i
]
pre_1[i]
pre1[i] 为最近关键点的编号。第二次终点是关键点（相当于是在反图上以关键点为起点跑），同样记两个值：
d
i
s
2
[
i
]
dis_2[i]
dis2[i] 和
p
r
e
2
[
i
]
pre_2[i]
pre2[i]。
然后我们可以枚举边
(
u
,
v
)
(u,v)
(u,v)，如果
p
r
e
1
[
u
]
≠
p
r
e
2
[
v
]
pre_1[u]\ne pre_2[v]
pre1[u]=pre2[v]，则以
d
i
s
1
[
u
]
+
w
(
u
,
v
)
+
d
i
s
2
[
v
]
dis_1[u]+w(u,v)+dis_2[v]
dis1[u]+w(u,v)+dis2[v] 更新答案。
时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn)。
code
#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std
;
typedef pair
<int,ll
>Pair
;
int n
,m
,k
,t
;
int a
[N
],tag
[N
],vis
[N
],pre1
[N
],pre2
[N
];
vector
<Pair
>G
[N
],rG
[N
];
ll dis1
[N
],dis2
[N
];
priority_queue
<Pair
>Q
;
void dijkstra(ll
*dis
,int *pre
){
memset(vis
,0,sizeof(vis
));
memset(dis
,0x3f,sizeof(ll
)*(n
+1));
for(int i
=1;i
<=k
;++i
)
dis
[a
[i
]]=0,pre
[a
[i
]]=a
[i
],Q
.push(Pair(0,a
[i
]));
while(!Q
.empty()){
int x
=Q
.top().second
;Q
.pop();
if(vis
[x
]) continue;vis
[x
]=1;
for(Pair
&now
:G
[x
]){
int to
=now
.first
;
if(dis
[to
]>dis
[x
]+now
.second
){
dis
[to
]=dis
[x
]+now
.second
;
pre
[to
]=pre
[x
],Q
.push(Pair(-dis
[to
],to
));
}
}
}
}
int main(){
int T
,u
,v
,w
;
scanf("%d",&T
);
while(T
--){
scanf("%d%d%d",&n
,&m
,&k
);
for(int i
=1;i
<=m
;++i
){
scanf("%d%d%d",&u
,&v
,&w
);
G
[u
].push_back(Pair(v
,w
)),rG
[v
].push_back(Pair(u
,w
));
}
for(int i
=1;i
<=k
;++i
) scanf("%d",&a
[i
]),tag
[a
[i
]]=1;
dijkstra(dis1
,pre1
);
for(int i
=1;i
<=n
;++i
) G
[i
]=rG
[i
];
dijkstra(dis2
,pre2
);
ll ans
=1e18;
for(int i
=1;i
<=n
;++i
)
for(Pair
&x
:G
[i
])
if(pre1
[x
.first
]&&pre2
[i
]&&pre1
[x
.first
]!=pre2
[i
])
ans
=min(ans
,dis1
[x
.first
]+dis2
[i
]+x
.second
);
printf("%lld\n",ans
);
for(int i
=1;i
<=n
;++i
) tag
[i
]=0,G
[i
].clear(),rG
[i
].clear(),pre1
[i
]=pre2
[i
]=0;
}
return 0;
}
