JOI2015本選-3.cpp

#include <bits/stdc++.h>
using namespace std;

#define times(n, i) uptil(0, n, i)
#define upto(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f); i <= _##i; i++)
#define uptil(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f); i < _##i; i++)
#define downto(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f); i >= _##i; i--)
#define downtil(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f); i > _##i; i--)
#define unless(c) if(!(c))
#define until(c) while(!(c))
#define loop while(true)

typedef long long Distance;
#define distance first
typedef int Square;
#define square second

int main(){
    int N, M, C;
    cin >> N >> M >> C;

    vector<vector<pair<Distance, Square>>> path(N, vector<pair<Distance, Square>>());
    Distance d_sum = 0;
    times(M, i){
        int A, B, D;
        cin >> A >> B >> D;
        A--; B--;
        path[A].push_back(make_pair(D, B));
        path[B].push_back(make_pair(D, A));
        d_sum += D;
    }

    vector<pair<Distance, Square>> dist(N, make_pair(-1, -1));
    priority_queue<pair<Distance, Square>, vector<pair<Distance, Square>>, greater<pair<Distance, Square>>> pyon;
    pyon.push(make_pair(0, 0));
    until(pyon.empty()){
        auto p = pyon.top(); pyon.pop();
        if(dist[p.square].distance != -1) continue;
        dist[p.square] = make_pair(p.distance, p.square);
        for(auto x : path[p.square]){
            if(dist[x.square].distance == -1)
                pyon.push(make_pair(dist[p.square].distance + x.distance, x.square));
        }
    }

    sort(dist.begin(), dist.end());
    vector<int> sort_order(N);
    times(N, i) sort_order[dist[i].square] = i;
    #ifndef EVAL
        times(N, i) cout << dist[i].square << ":" << dist[i].distance << " ";
        cout << endl;
    #endif

    long long cost = LLONG_MAX;
    Distance dcost = d_sum;

    times(N, i){
        for(auto p : path[dist[i].square]){
            if(sort_order[p.square] < sort_order[dist[i].square]) dcost -= p.distance;
        }
        #ifndef EVAL
            cout << i << " ccost:" << C * dist[i].distance << ", dcost: " << dcost << endl;
        #endif
        cost = min(cost, C * dist[i].distance + dcost);
    }
    cout << cost << endl;

    return 0;
}