CCF考试——201609-4交通规划

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

typedef struct edge{
    int vertex;
    long long cost;
    edge(int v,long long c){
        vertex = v;
        cost = c;
    }
}Edge;

struct cmp{
    bool operator() (Edge e1,Edge e2){
        return e1.cost>e2.cost;
    }
};

const long long MAX = 0x7ffffff;

int N,M;
int s,e;
long long c,ans;
vector<Edge> edges[100001];
int collect[100001];
long long dist[100001];
long long cost[100001];

void Dijikstra(int vertex)
{
    dist[vertex] = cost[vertex] = 0;
    priority_queue<Edge,vector<Edge>,cmp> q;
    q.push(Edge(vertex,0));
    while(!q.empty()){
        Edge tmp = q.top();
        q.pop();
        int v = tmp.vertex;
        if(!collect[v]){
            collect[v] = 1;
            for(int i = 0 ; i < edges[v].size() ; i++){
                int vv = edges[v][i].vertex;
                long long c = edges[v][i].cost;
                if(collect[vv]){
                    continue;
                }
                if(dist[vv] > dist[v]+c){
                    dist[vv] = dist[v]+c;
                    cost[vv] = c;
                    q.push(Edge(vv,dist[vv]));
                }
                if(dist[vv] == dist[v]+c){
                    cost[vv] = min(c,cost[vv]);
                }
            }
        }
    }
}

int main()
{
    while(cin>>N>>M){
        ans = 0;
        for(int i = 1 ; i <= N ; i++){
            collect[i] = 0;
            dist[i] = MAX;
            cost[i] = MAX;
        }
        for(int i = 0 ; i < M ; i++){
            cin>>s>>e>>c;
            edges[s].push_back(Edge(e,c));
            edges[e].push_back(Edge(s,c));
        }
        Dijikstra(1);
        for(int i = 1 ; i <= N ; i++){
            ans += cost[i];
        }   
        cout<<ans<<endl;
    }

    return 0;
 }