原题链接

学习一手jiangly哥哥的代码

dij取消vis的使用，采用优先队列<权重,点>的形式入队,代码简洁优美。
针对本题，采用奇数偶数分开的形式判断有无上马，增加一倍的顶点数。

再一次膜拜哥哥ing

建图

1
2
3
4
5
6
7
8
9
std::vector<std::vector<std::array<int, 2>>> adj(n);
for (int i = 0; i < m; i++) {
    int u, v, w;
    std::cin >> u >> v >> w;
    u--;
    v--;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}

dijkstra最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
auto dijkstra = [&](int s) {
    std::vector<i64> dis(2 * n, inf);
    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<>> pq;
    pq.emplace(0LL, 2 * s);
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (dis[u] != inf) {
            continue;
        }
        dis[u] = d;
        
        int x = u / 2;
        int t = u % 2;
        
        if (!t && horse[x]) {
            pq.emplace(d, 2 * x + 1);
        }
        
        for (auto [y, w] : adj[x]) {
            pq.emplace(d + (t ? w / 2 : w), 2 * y + t);
        }
    }
    
    std::vector<i64> d(n, inf);
    for (int i = 0; i < n; i++) {
        d[i] = std::min(dis[2 * i], dis[2 * i + 1]);
    }
    return d;
};

转换成普通dij模板如下

建图

1
2
3
4
5
6
vector<vector<pair<ll,ll>>> g(n+1);
while(m--){
    ll u,v,w;
    cin >> u >> v >> w;
    g[u].push_back({v,w});
}

dij本体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
auto dijkstra = [&](int s) {
    vector<ll> dis(n+1, INF);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
    pq.emplace(0LL, s);
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (dis[u] != INF) {
            continue;
        }
        dis[u] = d;
        
        for (auto [y, w] : g[u]) {
            pq.emplace(d + w, y );
        }
    }
    
    return dis;
};

使用

1
2
3
4
auto dis = dijkstra(s);
for(int i=1;i<=n;i++){
    cout<<dis[i]<<" \n"[i==n];
}

洛谷模板题测试，成功！