目录
显示
题目链接
https://www.luogu.com.cn/problem/P5304
题解
一种思路是建一个超级源点和超级汇点,将所有特殊点分为两个集合,求出从源点到汇点的最短路,这个最短路就是其中若干个特殊点对最短路的最小值。
然而只跑一次最短路并不能覆盖到任意的特殊点对,因此需要多次重新划分集合,取所有最短路的最小值作为答案。
一种可行的划分方式是这样的:考虑每个特殊点的编号 \(1,2,\ldots ,k\),对于每个二进制位,如果两个点在该位上的值相同,就分到同一个集合去。
这样需要跑 \(\log k\) 次最短路。
因为任意两个点的编号不同,故对于任意特殊两个点,都存在一个不同的二进制位,从而使得它们会划分到不同的集合去,从而影响最终的答案。
#include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; struct graph { struct edge { int v,w,next; }e[1000005]; struct node { int u; long long dis; bool operator<(const node&a)const { return dis>a.dis; } }; int head[100005],vis[100005],cnt; long long dis[100005]; int s,t; priority_queue<node> q; void init(int n) { memset(head,0,sizeof(head)); cnt=0; s=n+1,t=n+2; } void addedge(int u,int v,int w) { e[++cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt; } long long dijkstra() { memset(dis,63,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0; q.push({s,0}); while(!q.empty()) { int u=q.top().u; q.pop(); if(vis[u])continue; vis[u]=1; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(dis[v]>dis[u]+e[i].w) { dis[v]=dis[u]+e[i].w; q.push({v,dis[v]}); } } } return dis[t]; } }g,g1; int p[100005]; int main() { //ios::sync_with_stdio(false); int T; cin>>T; while(T--) { int n,m,k; cin>>n>>m>>k; g.init(n); g1.init(n); int s=n+1,t=n+2; for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g1.addedge(u,v,w); } for(int i=1;i<=k;i++) cin>>p[i]; long long ans=1e18; for(int i=0;(1<<i)<=k;i++) { g=g1; for(int j=1;j<=k;j++) if(j&(1<<i)) g.addedge(s,p[j],0); else g.addedge(p[j],t,0); ans=min(ans,g.dijkstra()); g=g1; for(int j=1;j<=k;j++) if(j&(1<<i)) g.addedge(p[j],t,0); else g.addedge(s,p[j],0); ans=min(ans,g.dijkstra()); } cout<<ans<<endl; } return 0; }