思路与算法

每条道路可双向通行，在邻接表中保存两条弧；平行道路分别保留。所有费用为正数，使用堆优化Dijkstra计算起点Ts到终点Te的最短费用。距离数组先设无穷，起点为0。每次取出堆中距离最小的候选，如果它不是当前最新距离就跳过；否则松弛所有相邻道路。终点被取出时距离已确定，可以结束。

正确性说明

保持每个有限距离都对应一条真实路径，因此它不会小于真正最短路。取出当前距离最小且未过时的顶点u时，如果有更短的路径到u，该路径上第一个尚未确定的顶点，其前驱已经确定，经过那条非负费用边松弛后应有不大于该路径长度的候选先被取出，与u当前最小矛盾。因此u的距离准确。不断松弛覆盖所有可能改善，最终终点得到最短费用。题目输出段的数据保证按起终点存在通路处理，全部测试输入也独立验证这一保证。

复杂度

初始化距离数组和邻接表O(T+C)。二叉堆使用惰性更新，每条弧可产生常数次松弛，堆项数量O(C)，总时间O((T+C) log(C+1))，空间O(T+C)。题目T<=2500、C<=6200，费用<=1000；简单最短路最多T-1条边，距离至多2499000，int足够，INF取10^9。起点等于终点时答案0。

易错点

道路双向；相同两站之间允许不同费用的平行边，样例已出现，不能只保留读到的最后一条。堆中旧距离要跳过。费用均为1至1000，不套用允许负边的版本。输出单个终点费用，不是所有顶点距离。最大测试保留每个非起终点至少两个不同邻居的原文结构条件，覆盖1000权值、2500点、6200边、平行边和同起终点。独立答案用队列Bellman-Ford，并对50个小图与Floyd闭包逐点交叉核验。

参考代码（C++11）

#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0, a, b, w; i < m; ++i) {
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    const int INF = 1000000000;
    vector<int> d(n + 1, INF);
    using Item = pair<int, int>;
    priority_queue<Item, vector<Item>, greater<Item>> q;
    d[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        int dist = q.top().first, u = q.top().second;
        q.pop();
        if (dist != d[u])
            continue;
        if (u == t)
            break;
        for (auto e : g[u])
            if (d[e.first] > dist + e.second) {
                d[e.first] = dist + e.second;
                q.push({d[e.first], e.first});
            }
    }
    cout << d[t] << '\n';
}