Pro4

原始文件为 CPP 代码，本文是转换后的 Markdown 文件。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
const int maxn = 10005;

int my_compare(int a, int b)
{
    if(a == -1) return 1;
    else if(b == -1) return -1;
    else if(a == b) return 0;
    else if(a > b) return 1;
    return -1;
}

struct Edge
{
    int from,to,dist;
    Edge(int u,int v,int d):from(u),to(v),dist(d){}
};

struct HeapNode
{
    int value,pos;
    HeapNode(int p,int v):pos(p),value(v){}
    bool operator < (const HeapNode& other) const
    {
        return value > other.value;
    }
};

struct Dijkstra
{
    vector<int> adjG[maxn];
    vector<Edge> edges;

    int n;
    int total;
    bool visit[maxn];
    int parent[maxn];
    int distance[maxn];
    int lastedge[maxn];

    void init(int n)
    {
        this->n = n;
        this->total = 0;
        for (int i = 0; i < n; ++i) adjG[i].clear();    
        for (int i = 0; i < n; ++i) lastedge[i] == -1;
        edges.clear();
    }

    void add_edge(int from,int to,int weight)
    {
        adjG[from].push_back(edges.size());
        edges.push_back(Edge(from,to,weight));
    }

    void dijkstra(int root) 
    {  
        priority_queue<HeapNode> Q;     
        for(int i = 0; i < n; i++) distance[i] = -1;  

        distance[root] = 0;  
        lastedge[root] = 0;
        memset(visit, 0, sizeof(visit));  
        Q.push((HeapNode){root, 0});  

        while(!Q.empty()) 
        {    
            HeapNode x = Q.top(); Q.pop();    
            int u = x.pos;    

            if(visit[u]) continue;   

            total += lastedge[u];
            visit[u] = true;    

            for(int i = 0; i < adjG[u].size(); i++) 
            {     
                Edge& e = edges[adjG[u][i]];      
                int update = my_compare(distance[e.to], distance[u] + e.dist);
            //  printf("%d %d %d %d\n",e.from,e.to,e.dist,update);          

                if(update == 1 || update == 0 && my_compare(lastedge[e.to],e.dist) == 1)
                {
                    distance[e.to] = distance[u] + e.dist;        
                    parent[e.to] = adjG[u][i];        
                    Q.push((HeapNode){e.to, distance[e.to]});     
                    lastedge[e.to] = e.dist;
                }       
            }  
        } 
    }
};

int main()
{
    //freopen("in.txt","r",stdin);
    Dijkstra d;

    int n,m;
    scanf("%d%d",&n,&m);
    d.init(n);

    for (int i = 0; i < m; ++i)
    {
        int from,to,weight;
        scanf("%d%d%d",&from,&to,&weight);

        d.add_edge(from-1,to-1,weight);
        d.add_edge(to-1,from-1,weight);
    //  printf("%d %d %d\n",from-1,to-1,weight);
    }
    d.dijkstra(0);

    cout << d.total << endl;

}