51Nod1443 路径和树

最短路径

51Nod

要建出一棵最短路树，先跑一边最短路，然后枚举找一下每个点的最短路是由哪一个点松弛过来的，然后就可以求出来了。

那么要求权值和最小的最短路树，一种暴力的想法是将 最短路图 求出来，再跑一遍 mst。但是可以发现，每个点的选择是互相独立的，所以只要记一下松弛过来的父边权值最小的边就可以了。

注意开long long

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
typedef long long LL;
#define int LL
const int INF = 0x7f7f7f7f;
const int MAXN = 3e5;
const int MAXM = 3e5;
int n, m, s, edge, ans;
int firstEdge[MAXN + 5], minF[MAXN + 5], dist[MAXN + 5];
struct Edge {
    int to, w, nxt;
    Edge(){}
    Edge(int x, int y, int z) {
        to = y;
        w = z;
        nxt = firstEdge[x];
    }
} e[MAXM * 2 + 5];
struct Heap {
    int x, y;
    Heap(){}
    Heap(int a, int b) {
        x = a;
        y = b;
    }
};
bool operator < (const Heap &a, const Heap &b) {
    return a.y > b.y;
}
std::priority_queue <Heap> q;
inline int read() {
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
inline void addEdge(int x, int y, int z) {
    e[++edge] = Edge(x, y, z);
    firstEdge[x] = edge;
}
void Dijkstra() {
    memset(dist, INF, sizeof(dist));
    dist[s] = 0;
    q.push(Heap(s, 0));
    while(!q.empty()) {
        Heap from = q.top();
        q.pop();
        if(from.y != dist[from.x]) continue;
        for(int k = firstEdge[from.x]; k; k = e[k].nxt) {
            int to = e[k].to, w = e[k].w;
            if(dist[to] > dist[from.x] + w) {
                dist[to] = dist[from.x] + w;
                q.push(Heap(to, dist[to]));
            }
        }
    }
}
signed main() {
    n = read();
    m = read();
    for(int i = 1; i <= m; ++i) {
        int a = read(), b = read(), c = read();
        addEdge(a, b, c);
        addEdge(b, a, c);
    }
    s = read();
    Dijkstra();
    memset(minF, INF, sizeof(minF));
    minF[s] = 0;
    for(int i = 1; i <= n; ++i) {
        for(int k = firstEdge[i]; k; k = e[k].nxt) {
            int to = e[k].to, w = e[k].w;
            if(dist[to] == dist[i] + w) minF[to] = std::min(minF[to], w);
        }
    }
    for(int i = 1; i <= n; ++i) ans += minF[i];
    printf("%lld\n", ans);
    return 0;
}