dijkstra算法c++, 使用模板类

下面是一个使用模板类实现的 C++ Dijkstra 算法示例代码：

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

const int INF = 0x3f3f3f3f; // 无穷大

template<typename T>
class Edge
{
public:
    int to;
    T cost;
    Edge(int to, T cost):to(to), cost(cost){}
};

template<typename T>
class Graph
{
public:
    vector<Edge<T>>* edges;
    int n;
    Graph(int n):n(n)
    {
        edges = new vector<Edge<T>>[n];
    }
    ~Graph()
    {
        delete[] edges;
    }
    void add_edge(int from, int to, T cost)
    {
        edges[from].push_back(Edge<T>(to, cost));
    }
};

template<typename T>
class Dijkstra
{
public:
    T* dist;
    bool* vis;
    int n;
    Graph<T>* graph;
    Dijkstra(Graph<T>* graph, int start):n(graph->n), graph(graph)
    {
        dist = new T[n];
        vis = new bool[n];
        memset(dist, INF, sizeof(T)*n);
        memset(vis, false, sizeof(bool)*n);
        dist[start] = 0;
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
        pq.push(make_pair(0, start));
        while(!pq.empty())
        {
            int u = pq.top().second;
            pq.pop();
            if(vis[u])
            {
                continue;
            }
            vis[u] = true;
            for(int i=0; i<graph->edges[u].size(); i++)
            {
                const Edge<T>& e = graph->edges[u][i];
                if(!vis[e.to] && dist[e.to]>dist[u]+e.cost)
                {
                    dist[e.to] = dist[u]+e.cost;
                    pq.push(make_pair(dist[e.to], e.to));
                }
            }
        }
    }
    ~Dijkstra()
    {
        delete[] dist;
        delete[] vis;
    }
};

int main()
{
    int n, m; // n 个节点，m 条边
    cin >> n >> m;
    Graph<int>* graph = new Graph<int>(n);
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        graph->add_edge(u, v, w);
        graph->add_edge(v, u, w);
    }
    int start;
    cin >> start;
    Dijkstra<int>* dijkstra = new Dijkstra<int>(graph, start);
    for(int i=0; i<n; i++)
    {
        if(dijkstra->dist[i]==INF)
        {
            cout << "INF" << endl;
        }
        else
        {
            cout << dijkstra->dist[i] << endl;
        }
    }
    delete dijkstra;
    delete graph;
    return 0;
}

该代码使用模板类实现 Dijkstra 算法，支持多种数据类型。同时，使用图的邻接表存储图，时间复杂度为 O(mlogn)，其中 n 为节点个数，m 为边数。