1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5const long long INF = 1e18;
6
7vector<pair<int, int>> adj[MAXN]; // 邻接表
8long long dist1[MAXN];  // 最短距离
9long long dist2[MAXN];  // 严格次短距离
10int cnt[MAXN];          // 每个顶点被确定的次数
11int n, m;
12
13void dijkstra(int s) {
14    for (int i = 1; i <= n; i++) {
15        dist1[i] = dist2[i] = INF;
16        cnt[i] = 0;
17    }
18    dist1[s] = 0;
19
20    // 小根堆：{距离, 顶点}
21    priority_queue<pair<long long, int>,
22                   vector<pair<long long, int>>,
23                   greater<>> pq;
24    pq.push({0, s});
25
26    while (!pq.empty()) {
27        auto [d, u] = pq.top();
28        pq.pop();
29
30        cnt[u]++;
31        // 每个顶点最多处理2次（最短和次短）
32        if (cnt[u] > 2) continue;
33
34        for (auto [v, w] : adj[u]) {
35            long long nd = d + w;
36
37            if (nd < dist1[v]) {
38                // 新距离比最短还短
39                dist2[v] = dist1[v]; // 原最短变为次短
40                dist1[v] = nd;
41                pq.push({nd, v});
42            } else if (nd > dist1[v] && nd < dist2[v]) {
43                // 严格大于最短，且比当前次短更短
44                dist2[v] = nd;
45                pq.push({nd, v});
46            }
47        }
48    }
49}
50
51int main() {
52    ios::sync_with_stdio(false);
53    cin.tie(nullptr);
54
55    int s, t;
56    cin >> n >> m >> s >> t;
57
58    for (int i = 0; i < m; i++) {
59        int u, v, w;
60        cin >> u >> v >> w;
61        adj[u].push_back({v, w});
62        adj[v].push_back({u, w}); // 无向图
63    }
64
65    dijkstra(s);
66
67    if (dist2[t] == INF)
68        cout << -1 << endl; // 不存在次短路
69    else
70        cout << dist2[t] << endl;
71
72    return 0;
73}

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5const long long INF = 1e18;
6
7vector<pair<int, int>> adj[MAXN];
8long long dist[MAXN][2]; // dist[v][0]=最短, dist[v][1]=次短
9int n, m;
10
11void dijkstra(int s) {
12    for (int i = 1; i <= n; i++) {
13        dist[i][0] = dist[i][1] = INF;
14    }
15    dist[s][0] = 0;
16
17    // {距离, 顶点, 类型(0=最短/1=次短)}
18    priority_queue<tuple<long long, int, int>,
19                   vector<tuple<long long, int, int>>,
20                   greater<>> pq;
21    pq.push({0, s, 0});
22
23    while (!pq.empty()) {
24        auto [d, u, type] = pq.top();
25        pq.pop();
26
27        // 如果当前距离已经过时，跳过
28        if (d > dist[u][type]) continue;
29
30        for (auto [v, w] : adj[u]) {
31            long long nd = d + w;
32
33            if (nd < dist[v][0]) {
34                dist[v][1] = dist[v][0];
35                dist[v][0] = nd;
36                pq.push({dist[v][0], v, 0});
37                pq.push({dist[v][1], v, 1});
38            } else if (nd > dist[v][0] && nd < dist[v][1]) {
39                dist[v][1] = nd;
40                pq.push({nd, v, 1});
41            }
42        }
43    }
44}