题目链接

Road Construction Aizu - 2249

思路

$$ 以最短路为前提，使花费最小。 $$

时间复杂度

$$ O(Mlog(N)) $$

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const long long INF = 1e18;

class Dij {
public:

    typedef long long T;

    // .first = v
    // .second.first.first = w;
    // .second.first.second = c;
    // .second.second = next;
    vector<int> head;
    typedef pair<int, pair< pair<T, T>, int> > P;
    vector<P> e;
    int tot;
    vector<T> dist;
    vector<T> cost;


    inline void init(int cnt_n, int cnt_m) {
        head.resize(cnt_n + 5);
        dist.resize(cnt_n + 5);
        cost.resize(cnt_n + 5);
        fill(head.begin(), head.end(), -1);
        e.resize(cnt_m * 2 + 10);
        tot = 0;
    }

    inline void add_edge(int u, int v, T w, T c) {
        e[tot] = make_pair(v, make_pair(make_pair(w, c), head[u]));
        head[u] = tot++;
    }

    inline void add_edges(int u, int v, T w, T c) {
        add_edge(u, v, w, c);
        add_edge(v, u, w, c);
    }


    void gao(int s) {
        priority_queue<pair<T, int>
                 , vector<pair<T, int> >
                 , greater<pair<T, int> > > sm;
        fill(dist.begin(), dist.end(), INF);
        fill(cost.begin(), cost.end(), INF);
        dist[s] = 0;
        cost[s] = 0;
        sm.push(make_pair(0, s));

        while (!sm.empty()) {
            pair<T, int> p = sm.top();
            sm.pop();
            int u = p.second;
            if (dist[u] < p.first) {
                continue;
            }
            for (int i = head[u]; ~i; i = e[i].second.second) {
                int v = e[i].first;
                T w = e[i].second.first.first;
                T c = e[i].second.first.second;
                if (dist[v] > dist[u] + w || (dist[v] == dist[u] + w && c < cost[v])) {
                    dist[v] = dist[u] + w;
                    cost[v] = c;
                    sm.push(make_pair(dist[v], v));
                }
            }
        }
    }
};

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m), n + m) {
        Dij dij;
        dij.init(n, m);
        while (m--) {
            int u, v, w, c;
            scanf("%d%d%d%d", &u, &v, &w, &c);// don't forget &
            dij.add_edges(u, v, w, c);
        }
        dij.gao(1);
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += dij.cost[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}