题解 | 旅途

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

class Solution {
public:
    int shortestPath(int n, vector<int>& harassment, vector<vector<int>>& roads) {
        // 建立邻接表
        vector<vector<pair<int, int>>> graph(n + 1);
        for (const auto& road : roads) {
            int u = road[0], v = road[1];
            // 边的权重为目标站点的搭讪次数
            graph[u].push_back({v, harassment[v-1]});
            graph[v].push_back({u, harassment[u-1]});
        }
        
        // 距离数组，初始化为无穷大
        vector<int> dist(n + 1, INT_MAX);
        dist[1] = harassment[0];  // 起点的搭讪次数
        
        // 优先队列，存储{距离, 节点}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.push({dist[1], 1});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue;
            
            // 遍历相邻节点
            for (auto [v, w] : graph[u]) {
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        
        return dist[n];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> harassment(n);
    for (int i = 0; i < n; i++) {
        cin >> harassment[i];
    }
    
    vector<vector<int>> roads(m, vector<int>(2));
    for (int i = 0; i < m; i++) {
        cin >> roads[i][0] >> roads[i][1];
    }
    
    Solution solution;
    cout << solution.shortestPath(n, harassment, roads) << endl;
    
    return 0;
}

import java.util.*;

class Solution {
    public int shortestPath(int n, int[] harassment, int[][] roads) {
        // 建立邻接表
        List<List<int[]>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 添加边
        for (int[] road : roads) {
            int u = road[0], v = road[1];
            // 边的权重为目标站点的搭讪次数
            graph.get(u).add(new int[]{v, harassment[v-1]});
            graph.get(v).add(new int[]{u, harassment[u-1]});
        }
        
        // 距离数组，初始化为无穷大
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = harassment[0];  // 起点的搭讪次数
        
        // 优先队列，存储{距离, 节点}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{dist[1], 1});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];
            
            if (d > dist[u]) continue;
            
            // 遍历相邻节点
            for (int[] next : graph.get(u)) {
                int v = next[0], w = next[1];
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        
        return dist[n];
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[] harassment = new int[n];
        for (int i = 0; i < n; i++) {
            harassment[i] = sc.nextInt();
        }
        
        int[][] roads = new int[m][2];
        for (int i = 0; i < m; i++) {
            roads[i][0] = sc.nextInt();
            roads[i][1] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.shortestPath(n, harassment, roads));
        
        sc.close();
    }
}

from heapq import heappush, heappop
from collections import defaultdict
from typing import List

class Solution:
    def shortest_path(self, n: int, harassment: List[int], roads: List[List[int]]) -> int:
        # 建立邻接表
        graph = defaultdict(list)
        for u, v in roads:
            # 边的权重为目标站点的搭讪次数
            graph[u].append((v, harassment[v-1]))
            graph[v].append((u, harassment[u-1]))
        
        # 距离数组，初始化为无穷大
        dist = [float('inf')] * (n + 1)
        dist[1] = harassment[0]  # 起点的搭讪次数
        
        # 优先队列，存储(距离, 节点)
        pq = [(dist[1], 1)]
        
        while pq:
            d, u = heappop(pq)
            
            if d > dist[u]:
                continue
            
            # 遍历相邻节点
            for v, w in graph[u]:
                if dist[v] > dist[u] + w:
                    dist[v] = dist[u] + w
                    heappush(pq, (dist[v], v))
        
        return dist[n]

def main():
    n, m = map(int, input().split())
    harassment = list(map(int, input().split()))
    
    roads = []
    for _ in range(m):
        u, v = map(int, input().split())
        roads.append([u, v])
    
    solution = Solution()
    print(solution.shortest_path(n, harassment, roads))

if __name__ == "__main__":
    main()