LOJ#3087. 「GXOI / GZOI2019」旅行者（最短路）

旧城等待， 2022-01-12 09:43 308阅读 0赞

## 题面 ##

[传送门][Link 1]

## 题解 ##

以所有的感兴趣的城市为起点，我们正着和反着各跑一边多源最短路。记\\(c\_\{0/1,i\}\\)分别表示正图/反图中离\\(i\\)最近的起点，那么对于每条边\\((u,v,w)\\)，如果\\(c\_\{0,u\}\\neq c\_\{1,v\}\\)，那么我们就用\\(d\_\{0,u\}+d\_\{1,v\}+w\\)更新答案

//minamoto #include<bits/stdc++.h> #define R register #define ll long long #define inline __inline__ __attribute__((always_inline)) #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } const int N=1e5+5,M=5e5+5; struct eg{int v,nx,w;}e[M];int head[N],tot; inline void add(R int u,R int v,R int w){e[++tot]={v,head[u],w},head[u]=tot;} struct EG{int u,v,w;}E[M];int c[2][N],st[N],n,m,k;ll d[2][N],res;bool vis[N]; struct node{ int u;ll d; inline node(R int uu,R ll dd):u(uu),d(dd){} inline bool operator <(const node &b)const{return d>b.d;} };priority_queue<node>q; void dij(int *c,ll *d){ memset(d,0x3f,(n+1)<<3),memset(c,0,(n+1)<<2),memset(vis,0,n+1); fp(i,1,k)q.push(node(st[i],d[st[i]]=0)),c[st[i]]=st[i]; while(!q.empty()){ int u=q.top().u;q.pop();if(vis[u])continue; go(u)if(cmin(d[v],d[u]+e[i].w))q.push(node(v,d[v])),c[v]=c[u]; } } int main(){ // freopen("testdata.in","r",stdin); for(int T=read();T;--T){ n=read(),m=read(),k=read(),res=1e18; for(R int i=1,u,v,w;i<=m;++i)u=read(),v=read(),w=read(),E[i]={u,v,w},add(u,v,w); fp(i,1,k)st[i]=read(); dij(c[0],d[0]); memset(head,0,(n+1)<<2),tot=0; fp(i,1,m)add(E[i].v,E[i].u,E[i].w); dij(c[1],d[1]); memset(head,0,(n+1)<<2),tot=0; for(R int i=1,u,v;i<=m;++i){ u=E[i].u,v=E[i].v; if(c[0][u]&&c[1][v]&&c[0][u]!=c[1][v])cmin(res,d[0][u]+d[1][v]+E[i].w); } printf("%lld\n",res); } return 0; }

转载于:https://www.cnblogs.com/bztMinamoto/p/10745111.html

[Link 1]: https://loj.ac/problem/3087