Loj3087 [GXOI / GZOI2019] 旅行者 【最短路扩展】

题面

SOL

法一 ：二进制分组 O ( m l o g 2 n ) O(mlog^2n) O(mlog2n)
预计得分：50-60

按二进制每一位 0/1 将特殊点分成两组，一组跑最短路，一组统计。一次的答案为两组之间的最小值。

由于任意两个不同的数，二进制总有一位不同，所以总有一个分组方式能够将两个特殊点分开。

法二： 两次最短路+染色 $O(mlogn)$
预计得分：100

把特殊点放在一个集合里，原图跑一次dij，反图跑一次dij，对于每个点记录由哪一个特殊点更新过来，（即最短路树上的祖先）枚举每一条边，若两边的点在两次染色中特殊点不同，用 $dis[u]+dis[v]+w<u,v>$更新答案‘

正确性：每一条可能最短的路都被至少一条边按照以上的方式计算了贡献。

CODE

#include
using namespace std;
#define sf scanf
#define pf printf
#define ll long long
#define cs const
#define ri register int
#define in red()
inline int red()
{int data=0;int w=1; char ch=0;ch=getchar();while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();if(ch=='-') w=-1,ch=getchar();while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();return data*w;
}
cs int N=1e5+10,M=2e6+10;
cs ll inf=1e17;
int head[N],cnt=0,to[M],nxt[M],w[M];
int n,m,p[N],K,st,col[2][N];
ll dis[2][N];
inline void addedge(int u,int v,int vl){nxt[++cnt]=head[u];head[u]=cnt;to[cnt]=v;w[cnt]=vl;
}
typedef pair<ll,int> pi;
set<pi> s;
struct edge{int u,v,w;
}e[M];
inline void dij(bool f){for(ri i=1;i<=n;++i)dis[f][i]=inf;s.insert(pi(dis[f][st]=0,st));while(!s.empty()){pi t=*s.begin();s.erase(t);int u=t.second;for(ri i=head[u];i;i=nxt[i]){int v=to[i];if(dis[f][v]>dis[f][u]+w[i]){s.erase(pi(dis[f][v],v));dis[f][v]=dis[f][u]+w[i];col[f][v]= u==st? v : col[f][u];s.insert(pi(dis[f][v],v));			}}}
}
inline void solve(){n=in;m=in;K=in;memset(col,0,sizeof (col));for(ri i=1;i<=m;++i)e[i].u=in,e[i].v=in,e[i].w=in;for(ri i=1;i<=K;++i)p[i]=in;st=0;cnt=0;memset(head,0,sizeof (head));for(ri i=1;i<=K;++i){addedge(st,p[i],0);}for(ri i=1;i<=m;++i)addedge(e[i].u,e[i].v,e[i].w);dij(0);cnt=0;memset(head,0,sizeof (head));for(ri i=1;i<=K;++i){addedge(st,p[i],0);}for(ri i=1;i<=m;++i)addedge(e[i].v,e[i].u,e[i].w);dij(1);ll ans=inf;for(ri i=1;i<=m;++i){if(e[i].u==e[i].v)continue;if(col[0][e[i].u]!=col[1][e[i].v])ans=min(ans,dis[0][e[i].u]+e[i].w+dis[1][e[i].v]);}cout<<ans<<'\n';
}
signed main(){int T=in;while(T--)solve();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！