牛客网16445题：Dijkstra算法解决共享单车问题

5小时前牛客题解19

一、题目解读

本题属于加权无向图中的最短路径变形问题，核心在于处理"步行"和"骑行"两种移动状态的切换。题目特色在于：

图中某些节点提供自行车
骑行状态下路径权重减半
需要动态判断最优移动方式这类状态机模型在图论算法面试中具有典型性，常见于大厂笔试环节。

二、解题思路分析

本解法采用改进的Dijkstra算法，关键点包括：

状态扩展：将每个节点拆分为"步行到达"和"骑行到达"两种状态
优先级队列：使用最小堆保证每次处理当前最短路径
状态转移：

步行状态可转为骑行（当节点有自行车时）
骑行状态保持优势权重（边权/2）

时空优化：通过智能状态合并控制空间复杂度为O(2N)

三、详细解题步骤

数据结构初始化

构建邻接表存储图结构
标记含自行车的节点
初始化距离数组为INF

Dijkstra算法
结果提取

比较终点n的两种状态距离
输出最小值（处理不可达情况）

四、完整代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;

const int MAXN = 1e5 + 5;
const ll INF = LLONG_MAX;

vector<pair<int, int>> adj[MAXN];
bool has_bike[MAXN] = {false};

struct State {
    ll dist;
    int node;
    bool has_bike;
    bool operator>(const State& other) const {
        return dist > other.dist;
    }
};
//Dijkstra算法
void dijkstra(int start, int n, vector<ll>& dist) {
    priority_queue<State, vector<State>, greater<State>> pq;
    dist.assign(2 * n + 2, INF);
    
    // 初始状态：步行到达起点
    dist[start] = 0;
    pq.push({0, start, has_bike[start]});
    
    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();
        
        ll current_dist = current.dist;
        int u = current.node;
        bool bike = current.has_bike;
        
        if (current_dist > dist[u + (bike ? n : 0)]) continue;
        
        for (auto &edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            
            // 步行状态
            if (!bike) {
                ll new_dist = current_dist + w;
                if (new_dist < dist[v]) {
                    dist[v] = new_dist;
                    pq.push({new_dist, v, has_bike[v]});
                }
            }
            
            // 骑车状态（包括新获得自行车的情况）
            bool new_bike = bike || has_bike[u];
            ll bike_dist = current_dist + (new_bike ? w / 2 : w);
            int bike_state = v + (new_bike ? n : 0);
            
            if (bike_dist < dist[bike_state]) {
                dist[bike_state] = bike_dist;
                pq.push({bike_dist, v, new_bike});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    
    int k;
    cin >> k;
    
    for (int i = 0; i < k; ++i) {
        int node;
        cin >> node;
        has_bike[node] = true;
    }
    
    vector<ll> dist(2 * n + 2, INF);
    dijkstra(1, n, dist);
    
    ll result = min(dist[n], dist[2 * n]);
    
    if (result == INF) {
        cout << -1 << endl;
    } else {
        cout << result << endl;
    }
    
    return 0;
}