题解：P13624 [ICPC 2024 APC] There and Back Again

ssy666666 · 2026-08-10 09:45:48 · 题解

首先，最短路一定会被选择。接着我们考虑返程时怎么选择道路。

此时，我们考虑返程怎么选。相当于是它必须至少经过一条最短路未经过的道路。考虑在跑最短路时顺手维护一下次短路，次短路需要保证不会出现 u \rightarrow v \rightarrow u 这种路线，其他路线都可行。这样它必然满足条件。

但是实际上，这种方案并不完全正确。由样例一可知，你实际上还可以选择在最短路经过的节点中，选择一条边权最小的未经过的边，然后走过去再走回来。这种情况枚举一下选的是哪条边即可。

AC Code

#include<bits/stdc++.h>
#define pii pair<int , int>
using namespace std ;
const int MAXN = 1e5 + 7 ;
const int INF = 1e9 + 7 ;
int n , m ;
struct Edge {
    int v , w ;
};

vector<Edge> dir[MAXN] ;

struct Node {
    int u , dis ;
    int from ;

    bool operator > (const Node& l) const {
        return dis > l.dis ;
    }
};

priority_queue<Node , vector<Node> , greater<Node> > p ;
int dis[MAXN][2] ;
bool vis[MAXN][2] ;
int lst[MAXN][2] ;
void Dijkstra() {
    p.push({1 , 0 , 0}) ;
    for (int i = 1 ; i <= n ; i ++) {
        dis[i][0] = dis[i][1] = INF ;
    }
    dis[1][0] = 0 ;

    while (!p.empty()) {
        Node now = p.top() ;
        p.pop() ;

        int u = now.u ;
        int d = now.dis ;
        bool r ;
        if (d == dis[u][0] and !vis[u][0] and lst[u][0] == now.from)    r = 0 ;
        else if (d == dis[u][1] and !vis[u][1] and lst[u][1] == now.from)   r = 1 ;
        else    continue ;

        vis[u][r] = 1 ;

        for (auto edge : dir[u]) {
            int v = edge.v , w = edge.w ;
            if (v == now.from)  continue ;

            if (dis[v][0] > dis[u][r] + w) {
                dis[v][1] = dis[v][0] ;
                dis[v][0] = d + w ;
                lst[v][0] = u ;
                p.push({v , dis[v][0] , u}) ;
            }
            else if (dis[v][1] > dis[u][r] + w) {
                dis[v][1] = d + w ;
                lst[v][1] = u ;
                p.push({v , dis[v][1] , u}) ;
            }
        }
    }

    return ;
}

map<pii , int> h ;
bool us[MAXN] ;
signed main()
{
//  freopen("" , "r" , stdin) ;
//  freopen("" , "w" , stdout) ;

    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    cin >> n >> m ; 

    int mi = INF ;
    for (int i = 1 ; i <= m ; i ++) {
        int u , v , w ;
        cin >> u >> v >> w ;
        dir[u].push_back({v , w}) ;
        dir[v].push_back({u , w}) ;

        mi = min(mi , w) ;
    }

    if (n == 1) {
        if (mi == INF) {
            cout << -1 ;
            return 0 ;
        }
        else {
            cout << mi ;
            return 0 ;
        }
    }

    Dijkstra() ;

    int ans = dis[n][0] ;
    if (dis[n][0] == INF) {
        cout << -1 ;
        return 0 ;
    }

    int now = n ;
    while (now != 1) {
        h[{lst[now][0] , now}] = 1 ;
        us[now] = 1 ;
        now = lst[now][0] ;
    }
    us[1] = 1 ;

    int cnt = dis[n][0] ;
    mi = INF ;
    for (int i = 1 ; i <= n ; i ++) {
        for (auto edge : dir[i]) {
            if (h[{edge.v , i}] or h[{i , edge.v}] or (!us[i] and !us[edge.v])) {
                continue ;
            }

            mi = min(mi , edge.w) ;
        }
    }

    if (mi == INF and dis[n][1] == INF) {
        cout << -1 ;
        return 0 ;
    }

    cnt += mi * 2 ;
    cnt = min(cnt , dis[n][1]) ;
    cout << ans + cnt ;

    return 0 ;
}