A50247.午枫的双向奔赴 题解

约定：从 $u$ 走到 $v$ 的最短路长度 $L$ 记作 $L=u \rightarrow v$。

如果我们知道 $L_1=1 \rightarrow k$ 和 $L_2=n \rightarrow k$，那么他们需要多长时间才能见面呢？显然，有一个人会先到，然后等待另一个人到。所以是 $\max(L_1,l_2)$。

如果我们对于所有的 $k$ 都能知道 $L_1,L_2$ 的话，就可以 $O(n)$ 打擂台求出最短时间了。当然求出编号也不是难事，以后不再赘述。

很显然，$L_1$ 可以跑一遍单源最短路，$L_2$ 同样可以。

所以我们跑两遍单源最短路就行了！

时间复杂度：$O((n+m) \log m)$

空间复杂度：$O(n+m)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
const ll MAXN=2e5+25;
struct node{
    ll nxt,to,w;
};
ll n,m,u,v,w,tot,ans=LLONG_MAX;
ll hd[MAXN],dist[2][MAXN];
bool vis[MAXN];
node edge[MAXN<<1];
priority_queue<pll,vector<pll>,greater<pll>> pq;
inline void add(const ll &u,const ll &v,const ll &w){
    edge[++tot]={hd[u],v,w};
    hd[u]=tot;
    return;
}
inline void dij(const ll &r,const ll &beg){
    pll u,v;
    memset(dist[r],0x3f,sizeof(dist[r]));
    memset(vis,false,sizeof(vis));
    dist[r][beg]=0;
    pq.push(mkp(0,beg));
    while(!pq.empty()){
        u=pq.top();
        pq.pop();
        if(vis[u.se]) continue;
        vis[u.se]=true;
        for(ll i=hd[u.se];i;i=edge[i].nxt){
            v=mkp(u.fi+edge[i].w,edge[i].to);
            if(v.fi<dist[r][v.se]){
                dist[r][v.se]=v.fi;
                if(vis[v.se]) continue;
                pq.push(v);
            }
        }
    }
    return;
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dij(0,1);
    dij(1,n);
    for(ll i=1;i<=n;i++) ans=min(max(dist[0][i],dist[1][i]),ans);
    cout<<ans<<'\n';
    for(ll i=1;i<=n;i++) if(max(dist[0][i],dist[1][i])==ans) cout<<i<<' ';
    return 0;
}