题解 | #共享单车#

解题思路

这是一个最短路径问题，但有以下特殊条件：

1. 图中某些节点有共享单车
2. 如果骑单车，边的权重会变为原来的一半
3. 一旦获得单车就可以一直使用
4. 需要从节点1到达节点 ，如果不可达则输出-1

解决方案：

1. 使用Dijkstra算法的变体
2. 状态需要记录：(节点编号, 是否有单车)
3. 使用优先队列优化
4. 对每个节点维护两种状态的最短距离：有车到达的最短距离和无车到达的最短距离

代码

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long val;      // 当前路径长度
    int index;     // 当前节点编号
    bool has_bike; // 是否有单车
};

class CompareNode {
public:
    bool operator()(const Node& lhs, const Node& rhs) const {
        return lhs.val > rhs.val;
    }
};

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 建图
    vector<vector<pair<int,int>>> graph(n+1);
    for(int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    
    // 记录有单车的节点
    vector<bool> has_bike(n+1, false);
    int k;
    scanf("%d", &k);
    for(int i = 0; i < k; i++) {
        int id;
        scanf("%d", &id);
        has_bike[id] = true;
    }
    
    // 初始化访问数组
    vector<vector<long>> visit(n+1, vector<long>(2, LONG_MAX));
    visit[1][has_bike[1]] = 0;
    
    // Dijkstra算法
    priority_queue<Node, vector<Node>, CompareNode> q;
    q.push({0, 1, has_bike[1]});
    
    while(!q.empty()) {
        Node curr = q.top();
        q.pop();
        
        if(curr.index == n) {
            printf("%ld\n", curr.val);
            return 0;
        }
        
        for(auto& [next, weight] : graph[curr.index]) {
            long time = curr.val + (curr.has_bike ? weight/2 : weight);
            bool next_has_bike = curr.has_bike || has_bike[next];
            
            if(time < visit[next][next_has_bike]) {
                visit[next][next_has_bike] = time;
                q.push({time, next, next_has_bike});
            }
        }
    }
    
    printf("-1\n");
    return 0;
}

import java.util.*;

public class Main {
    static class Node {
        long val;
        int index;
        boolean hasBike;
        
        Node(long val, int index, boolean hasBike) {
            this.val = val;
            this.index = index;
            this.hasBike = hasBike;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        // 建图
        List<List<int[]>> graph = new ArrayList<>(n + 1);
        for(int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for(int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            graph.get(u).add(new int[]{v, w});
            graph.get(v).add(new int[]{u, w});
        }
        
        // 记录有单车的节点
        boolean[] hasBike = new boolean[n + 1];
        int k = sc.nextInt();
        for(int i = 0; i < k; i++) {
            hasBike[sc.nextInt()] = true;
        }
        
        // 初始化访问数组
        long[][] visit = new long[n + 1][2];
        for(long[] row : visit) {
            Arrays.fill(row, Long.MAX_VALUE);
        }
        visit[1][hasBike[1] ? 1 : 0] = 0;
        
        // Dijkstra算法
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> Long.compare(a.val, b.val));
        pq.offer(new Node(0, 1, hasBike[1]));
        
        while(!pq.isEmpty()) {
            Node curr = pq.poll();
            
            if(curr.index == n) {
                System.out.println(curr.val);
                return;
            }
            
            for(int[] next : graph.get(curr.index)) {
                long time = curr.val + (curr.hasBike ? next[1]/2 : next[1]);
                boolean nextHasBike = curr.hasBike || hasBike[next[0]];
                
                if(time < visit[next[0]][nextHasBike ? 1 : 0]) {
                    visit[next[0]][nextHasBike ? 1 : 0] = time;
                    pq.offer(new Node(time, next[0], nextHasBike));
                }
            }
        }
        
        System.out.println(-1);
    }
}

import heapq
from collections import defaultdict

def solve():
    n, m = map(int, input().split())
    
    # 建图
    graph = defaultdict(list)
    for _ in range(m):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # 记录有单车的节点
    has_bike = [False] * (n + 1)
    k = int(input())
    for _ in range(k):
        has_bike[int(input())] = True
    
    # 初始化访问数组
    visit = [[float('inf')] * 2 for _ in range(n + 1)]
    visit[1][has_bike[1]] = 0
    
    # Dijkstra算法
    pq = [(0, 1, has_bike[1])]  # (距离, 节点, 是否有车)
    
    while pq:
        val, curr, curr_has_bike = heapq.heappop(pq)
        
        if curr == n:
            print(val)
            return
            
        for next_node, weight in graph[curr]:
            time = val + (weight // 2 if curr_has_bike else weight)
            next_has_bike = curr_has_bike or has_bike[next_node]
            
            if time < visit[next_node][next_has_bike]:
                visit[next_node][next_has_bike] = time
                heapq.heappush(pq, (time, next_node, next_has_bike))
    
    print(-1)

solve()

算法及复杂度

• 算法：Dijkstra最短路径算法的变体
• 时间复杂度： - 是节点数， 是边数
• 空间复杂度： - 需要存储访问数组和优先队列