题目链接:https://www.51nod.com/Challenge/Problem.html#!#problemId=1443

  • 时间限制 2 秒 空间限制 131,072 KB

题目描述

给定一幅无向带权连通图G = (V, E) (这里V是点集，E是边集)。从点u开始的最短路径树是这样一幅图G1 = (V, E1)，其中E1是E的子集，并且在G1中，u到所有其它点的最短路径与他在G中是一样的。
现在给定一幅无向带权连通图G和一个点u。你的任务是找出从u开始的最短路径树，并且这个树中所有边的权值之和要最小。

输入

单组测试数据。
第一行有两个整数n和m(1 ≤ n ≤ 3*10^5, 0 ≤ m ≤ 3*10^5)，表示点和边的数目。
接下来m行，每行包含3个整数 ui, vi, wi ，表示ui和vi之间有一条权值为wi的无向边(1 ≤ ui,vi ≤ n, 1 ≤ wi ≤ 10^9)。
输入保证图是连通的。
最后一行给出一个整数u (1 ≤ u ≤ n)，表示起点。

输出

输出这棵树的最小的权值之和。

输入样例

3 3
1 2 1
2 3 1
1 3 2
3

输出样例

2

解题思路

首先先跑一遍最短路，最短路上的边构成最短路径树，然后在最短路径树里跑一遍最小生成树就行了。实际上只要求出除起点外每个点选出最短的边加起来就行了。

#include <queue>
#include <cstring>
#include <iostream>
#define N 300005
using namespace std;
struct edge {
    int u, v, w;
}e[2 * N];
long long dis[N];
int cnt = 0, pre[N], vis[N], f[N];
void Add(int u, int v, int w)
{
    e[++cnt] = (edge){f[u], v, w};
    f[u] = cnt;
}
void Spfa(int s, int n)
{
    int t, v;
    queue <int> Q;
    Q.push(s);
    vis[s] = 1;
    dis[s] = 0;
    while (!Q.empty())
    {
        t = Q.front();
        Q.pop();
        vis[t] = 0;
        for (int i = f[t]; i; i = e[i].u)
        {
            v = e[i].v;
            if (dis[v] > dis[t] + e[i].w)
            {
                dis[v] = dis[t] + e[i].w;
                pre[v] = e[i].w;
                if (!vis[v])
                {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
            else if (dis[v] == dis[t] + e[i].w)
                pre[v] = min(pre[v], e[i].w);
        }
    }
}
int main()
{
    long long ans = 0;
    int n, m, s, u, v, w;
    scanf("%d%d", &n, &m);
    memset(dis, 15, sizeof(dis));
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        Add(u, v, w);
        Add(v, u, w);
    }
    scanf("%d", &s);
    Spfa(s, n);
    for (int i = 1; i <= n; i++)
        if (i != s)
            ans += (long long)pre[i];
    printf("%lld\n", ans);
    return 0;
}