官方题解

T5 午枫的双向奔赴

题目大意

给定一张图，小午和小枫分别在 $1$ 号节点和 $n$ 号节点，求出两人会和的最小时间，并且按照编号从小到大输出所有花费最小时间的节点

题解思路

设 $d1_i$ 为从 $1$ 号节点出发到达 $i$ 号节点的最短时间，$dn_i$ 为从 $n$ 号节点出发到达 $i$ 号节点的最短时间。那么他们在 $i$ 号节点会和花费的时间为 $max(d1_i,dn_i)$ 。所以他们会和的最短时间为 $\min_{i=1}^{n} (max(d1_i,dn_i))$ 。

分别以 $1$ 号节点和 $n$ 号节点为起始节点用 $dijkstra$ 求出最短路，即 $d1_i$ 和 $dn_i$ ，然后再求出他们会和需要的最短时间，最后找出所需最短时间的节点，按照编号从小到大输出。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define int long long
#define endl '\n'
const int INF = 1e18+10;

void solve(){
    int n,m;cin>>n>>m;
    vector<vector<PII>>v(n+1);
    for(int i=1;i<=m;i++){
        int a,b,c;cin>>a>>b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }

    auto DJ=[&](int bg,vector<int> &d){
        priority_queue<PII,vector<PII>,greater<PII>>q;
        vector<bool>st(n+1);
        d[bg]=0;
        q.push({d[bg],bg});
        
        while(!q.empty()){
            auto [_,t]=q.top();q.pop();
            if(st[t]) continue;
            st[t]=true;

            for(auto [x,c]:v[t]){
                if(d[x]>d[t]+c){
                    d[x]=d[t]+c;
                    q.push({d[x],x});
                }
            }
        }
    };

    vector<int>d1(n+1,INF),d2(n+1,INF);
    DJ(1,d1);
    DJ(n,d2);

    int mi=INF;
    for(int i=1;i<=n;i++){
        mi=min(mi,max(d1[i],d2[i]));
    }

    vector<int>res;
    for(int i=1;i<=n;i++){
        if(max(d1[i],d2[i])==mi) res.push_back(i);
    }
    sort(res.begin(),res.end());

    cout<<mi<<endl;
    for(auto x:res) cout<<x<<" ";
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}