当前位置：首页 > 牛客 > 牛客16445题：用Dijkstra算法解决骑车与步行最短路径问题

牛客16445题：用Dijkstra算法解决骑车与步行最短路径问题

3个月前 (09-16)

一、题目解读

牛客16445题要求解决一个图的最短路径问题：给定一个有向图，部分节点可获取自行车，骑行时边权减半，需在两种模式下（步行/骑车）计算从起点到终点的最短距离。题目难点在于状态转换与边权动态处理。

二、解题思路

1. 状态压缩：将节点分为“步行状态”和“骑车状态”，用节点编号偏移量表示（如原节点n扩展为n和n+n两种状态）。

2. Dijkstra算法：利用优先队列维护当前最短路径状态，通过松弛操作更新子节点距离。

3. 动态边权处理：骑行时边权减半，需判断当前是否持有自行车（通过has_bike数组或状态标记）。

4. 优化剪枝：若当前状态距离已劣于已知最短距离，直接跳过，避免无效扩展。

三、解题步骤

1. 初始化图结构，读取节点数m、边数n及自行车节点标记。

2. 构建邻接表adj存储边信息（节点v, 边权w）。

3. 定义状态结构体State（距离dist、节点node、是否骑车has_bike），重载比较运算符适配优先队列。

4. 执行Dijkstra算法：

○ 初始状态：起点步行距离为0，入队。

○ 循环弹出队首状态，遍历邻接边：

a. 步行状态：更新普通节点距离。

b. 骑车状态：若当前可骑车（原有自行车或当前节点可获取），计算减半边权并更新扩展状态。

○ 剪枝：若当前状态已劣于已知最短距离，跳过。

5. 最终距离为终点骑车/步行状态的最小值。

四、代码和注释

#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;
    }
};

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;
}