Dijkstra算法模板题 [USACO09OCT]热浪Hea

题目链接(中文版)
关于讲解，链接里点击题解，有很多讲解不错，这里我就不放思路了，感兴趣可以去看。
附上代码，以供自己复习

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

const int inf = 0x7fffffff;
const int maxnt = 6210;

int T, C, Ts, Te;

struct Edge{
    int from, to, weight;
    Edge(int u, int v, int w):from(u), to(v), weight(w){}
};

struct heap_node{
    int d, u;
    inline bool operator < (const heap_node& ob) const {
        return d > ob.d;
    }
};

struct Dijkstra{
    int n, m;
    int dis[maxnt], pre[maxnt], vis[maxnt];
    vector<Edge> edges;
    vector<int> g[maxnt];

    void init(int n){
        this->n = n;
        for (int i = 0; i < n; ++i)
            g[i].clear();
        edges.clear();
    }
    
    void add_edge(int u, int v, int w){
        edges.push_back(Edge(u, v, w));
        m = edges.size();
        g[u].push_back(m - 1);
    }

    void dijkstra(int s){
        for (int i = 1; i <= n; ++i)
            dis[i] = inf;
        dis[s] = 0;
        priority_queue<heap_node> que;
        memset(vis, 0, sizeof(vis));
        que.push((heap_node){0, s});
        while (!que.empty()){
            heap_node x = que.top();
            que.pop();
            int u = x.u;
            if (vis[u])
                continue;
            vis[u] = true;
            for (int i = 0; i < g[u].size(); ++i){
                Edge &e = edges[g[u][i]];
                if (dis[e.to] > dis[u] + e.weight){
                    dis[e.to] = dis[u] + e.weight;
                    pre[e.to] = g[u][i];
                    que.push((heap_node){dis[e.to], e.to});
                }
            }
        }
    }
};

int main(int argc, char const *argv[]){
    ios::sync_with_stdio(false);
    //freopen("/Users/macbook/Downloads/testdata (1).in", "r", stdin);
    Dijkstra dij;
    cin>>T>>C>>Ts>>Te;
    dij.init(T);
    int rs, re, ci;
    for (int i = 0; i < C; ++i){
        cin>>rs>>re>>ci;
        dij.add_edge(rs, re, ci);
        dij.add_edge(re, rs, ci);
    }
    dij.dijkstra(Ts);
    cout<<dij.dis[Te]<<endl;
    return 0;
}