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

一、题目解读

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

1. 图中某些节点提供自行车

2. 骑行状态下路径权重减半

3. 需要动态判断最优移动方式 这类状态机模型在图论算法面试中具有典型性，常见于大厂笔试环节。

二、解题思路分析

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

1. 状态扩展：将每个节点拆分为"步行到达"和"骑行到达"两种状态

2. 优先级队列：使用最小堆保证每次处理当前最短路径

3. 状态转移：

• 步行状态可转为骑行（当节点有自行车时）

• 骑行状态保持优势权重（边权/2）

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

三、详细解题步骤

1. 数据结构初始化

• 构建邻接表存储图结构

• 标记含自行车的节点

• 初始化距离数组为INF

2. Dijkstra算法

3. 结果提取

• 比较终点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;
}

五、算法总结

本题解通过状态机思想扩展传统Dijkstra算法，完美处理了移动方式切换带来的复杂度。该解法具有：

• 时间复杂度：O(MlogN) （与标准Dijkstra同阶）

• 空间复杂度：O(N+M)

• 适用场景：所有边权非负的加权图

• 可扩展性：可适配其他状态依赖型最短路径问题