ACM模版
这个题是单源最短路 + 最小生成树。
首先我们来介绍一下题中所述的最短路径树是什么,我们都知道,给定一个 uu 求单源最短路时,所有的最短路路径通常能够恰好构成一棵树,那么这棵树就是最短路径树。
可是我们这里为什么还要用最小生成树呢?这很容易理解,前文我提到,通常可以构成一棵树,那就自然有不通常的情况,如果从 u 到达一个结点 v 的最短路径不唯一呢?所以我们应该获取所有的最短路径边,从这些边中进行最小生成树,当然,这里有一个优化,当这些边数刚好等于结点数减一时,就不用生成树了。
这时我们考虑,我们如何获取最短路径呢?自然是通过单源最短路中的 dist[] 来获取,这里大概不能直接在求单源最短路时存储最短路径,因为那样就无法获取所有的最短路径了。
约莫就是这些,其实有一点我无法确定并且证明,就是如果对于这种不通常的情况,是否是取任何一条最短路都合法呢?如果是这样,那么最小生成树部分不就可以省去了吗?
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 10;
int n, m;
int vis[MAXN];
int pre[MAXN];
int bz[MAXN];
ll dist[MAXN];
vector<pair<int, ll> > vpil[MAXN];
queue<int> qi;
struct Edge
{
int u, v;
ll cost;
Edge(int U = -1, int V = -1, ll C = -1)
{
u = U;
v = V;
cost = C;
}
bool operator < (const Edge &x) const
{
return cost < x.cost;
}
};
vector <Edge> edge;
int find(int x)
{
if (x == pre[x])
{
return x;
}
else
{
return pre[x] = find(pre[x]);
}
}
void merge(int x, int y)
{
x = find(x);
y = find(y);
if (x == y)
{
return ;
}
pre[x] = pre[y];
}
void spfa(int star)
{
memset(dist, -1, sizeof(dist));
memset(vis, 0, sizeof(vis));
while (!qi.empty())
{
qi.pop();
}
dist[star] = 0;
vis[star] = 1;
qi.push(star);
while (!qi.empty())
{
int now = qi.front();
qi.pop();
vis[now] = 0;
int sz = (int)vpil[now].size();
for (int i = 0; i < sz; i++)
{
int v = vpil[now][i].first;
ll cost = vpil[now][i].second;
if (dist[v] == -1 || dist[v] > dist[now] + cost)
{
dist[v] = dist[now] + cost;
if (!vis[v])
{
vis[v] = 1;
qi.push(v);
}
}
}
}
}
ll Kruskal()
{
ll ret = 0;
memset(bz, 0, sizeof(bz));
sort(edge.begin(), edge.end());
int sz = (int)edge.size();
for (int i = 0; i < sz; i++)
{
int u = edge[i].u, v = edge[i].v;
ll cost = edge[i].cost;
if (bz[v] || find(u) == find(v))
{
continue;
}
bz[v] = 1;
merge(u, v);
ret += cost;
}
return ret;
}
int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = 0; i <= n; i++)
{
vpil[i].clear();
pre[i] = i;
}
int u, v, cost;
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &u, &v, &cost);
vpil[u].push_back(make_pair(v, (ll)cost));
vpil[v].push_back(make_pair(u, (ll)cost));
}
int star;
scanf("%d", &star);
spfa(star);
edge.clear();
for (int i = 1; i <= n; i++)
{
int sz = (int)vpil[i].size();
for (int j = 0; j < sz; j++)
{
int v = vpil[i][j].first;
ll cost = vpil[i][j].second;
if (dist[v] == dist[i] + cost)
{
edge.push_back(Edge(i, v, cost));
}
}
}
printf("%lld\n", Kruskal());
}
return 0;
}