【題解】ZeroJudge b117: TOI2008 4. 地道問題

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

const int maxn = 1000005;
int n, m, inf = 1e9, dis[maxn];
long long ans;
vector < pair<int, int> > out[maxn], in[maxn];

int main() {
    while (cin >> n >> m){
        for (int i = 1; i <= n; i++){
            dis[i] = inf;
            out[i].clear();
            in[i].clear();
        }
        for (int i = 0, a, b, w; i < m; i++){
            cin >> a >> b >> w;
            out[a].push_back({b, w});
            in[b].push_back({a, w});
        }
        ans = 0;
        priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
        pq.push({0, 1});
        
        dis[1] = 0;
        while (!pq.empty()){
            int x = pq.top().second, y = pq.top().first;
            pq.pop();
            if (dis[x] != y) continue;
            ans += dis[x];
            //cout << "1 -> " << x << " : " << dis[x] << "\n";
            for (auto i:out[x]){
                if (dis[i.first] > dis[x]+i.second){
                    dis[i.first] = dis[x]+i.second;
                    pq.push({dis[i.first], i.first});
                }
            }
        }
        //cout << ans << "\n";
        pq.push({0, 1});
        for (int i = 1; i <= n; i++){
            dis[i] = inf;
        }
        dis[1] = 0;
        while (!pq.empty()){
            int x = pq.top().second, y = pq.top().first;
            pq.pop();
            if (dis[x] != y) continue;
            ans += dis[x];
            //cout << "1 <- " << x << " : " << dis[x] << "\n";
            for (auto i:in[x]){
                if (dis[i.first] > dis[x]+i.second){
                    dis[i.first] = dis[x]+i.second;
                    pq.push({dis[i.first], i.first});
                }
            }
        }
        cout << ans << "\n";
    }
}