51nod11443-路径和树（图论，最短路，最小生成树）

1443 路径和树

题目来源： CodeForces

基准时间限制：1.5 秒空间限制：131072 KB 分值: 160 难度：6级算法题

关注

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

现在给定一幅无向带权连通图G和一个点u。你的任务是找出从u开始的最短路径树，并且这个树中所有边的权值之和要最小。

Input

单组测试数据。
第一行有两个整数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)，表示起点。

Output

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

Input示例

Output示例

  1 /*
  2 利用spfa求出最短路之后， 然后根据dist数组中的值去寻找某个点最短路径的上一条边，然后对这些边求最小生成树
  3 这里会出现一个问题，是否在求出每个点的最短路的上一条边之后，这个子图就变成了一个最小生成树了呢？
  4 有可能，但也有可能出现这种情况：
  5 某个点到起点的最短路可以通过多种路径实现，这种情况下，但是如果不用最小生成树的话，无法确定最小生成树中是哪一条路径
  6 因此需要求最短路
  7 ex:
  8 6 8
  9 1 2 30
 10 1 3 20
 11 2 3 50
 12 4 2 100
 13 2 5 40
 14 3 5 10
 15 3 6 50
 16 5 6 60
 17 4
 18 答案为：
 19 230
 20 */
 21 #include<bits/stdc++.h>
 22 #define LL long long
 23 #define MAXN 300005
 24 using namespace std;
 25 int n, m;
 26 LL dist[MAXN];
 27 int inQueue[MAXN], root[MAXN];
 28 int in[MAXN];
 29 vector <pair< int, LL> > G[MAXN];
 30 queue <int> Q;
 31 struct Edge
 32 {
 33     int u, v;
 34     LL cost;
 35     Edge(int U = -1, int V = -1, LL C = -1)
 36     {
 37         u = U;
 38         v = V;
 39         cost = C;
 40     }
 41     bool operator < (const Edge& x) const
 42     {
 43         return cost < x.cost;
 44     }
 45 };
 46 vector <Edge> edge;
 47 int findRoot(int x)
 48 {
 49     if(x == root[x]) return x;
 50     else
 51         return root[x] = findRoot(root[x]);
 52 }
 53 void unite(int x, int y)
 54 {
 55     x = findRoot(x);
 56     y = findRoot(y);
 57     if(x == y) return;
 58     root[x] = root[y];
 59 }
 60 void spfa(int star)
 61 {
 62     memset(dist, -1, sizeof(dist));
 63     memset(inQueue, 0, sizeof(inQueue));
 64     while(!Q.empty()) Q.pop();
 65     dist[star] = 0;
 66     inQueue[star] = 1;
 67     Q.push(star);
 68     while(!Q.empty())
 69     {
 70         int now = Q.front();
 71         Q.pop();
 72         inQueue[now] = 0;
 73         int siz = G[now].size();
 74         for(int i = 0; i < siz; i++)
 75         {
 76             int v = G[now][i].first;
 77             LL cost = G[now][i].second;
 78             if(dist[v] == -1 || dist[v] > dist[now] + cost)
 79             {
 80                 dist[v] = dist[now] + cost;
 81                 if(!inQueue[v])
 82                 {
 83                     inQueue[v] = 1;
 84                     Q.push(v);
 85                 }
 86             }
 87         }
 88     }
 89 }
 90 LL Kruskal()
 91 {
 92     LL res = 0;
 93     memset(in, 0, sizeof(in));
 94     sort(edge.begin(), edge.end());
 95     int siz = edge.size();
 96     for(int i = 0; i < siz; i++)
 97     {
 98         int u = edge[i].u, v = edge[i].v;
 99         LL cost = edge[i].cost;
100         if(in[v] || findRoot(u) == findRoot(v)) continue;
101         in[v] = 1;
102         unite(u, v);
103         res += cost;
104     }
105     return res;
106 }
107 int main()
108 {
109     freopen("data.in","r",stdin);
110     while(scanf("%d%d", &n, &m) != EOF)
111     {
112         for(int i = 0; i <= n; i++)
113         {
114             G[i].clear();
115             root[i] = i;
116         }
117         for(int i = 0; i < m; i++)
118         {
119             int u, v, cost;
120             scanf("%d%d%d", &u, &v, &cost);
121             G[u].push_back(make_pair(v, (LL)cost));
122             G[v].push_back(make_pair(u, (LL)cost));
123         }
124         int star;
125         scanf("%d", &star);
126         spfa(star);
127         edge.clear();
128         LL sum=0;
129 //        cout<<star<<endl;
130 //        for(int i=1;i<=n;i++){
131 //            cout<<dist[i]<<"	";
132 //        }
133 //        cout<<endl;
134         for(int i = 1; i <= n; i++)
135         {
136             //cout<<22222<<endl;
137             ///if(i!=star){
138                 int siz = G[i].size();
139                 //cout<<siz<<endl<<endl;
140                 for(int j = 0; j < siz; j++)
141                 {
142 
143                     int v = G[i][j].first;
144                     LL cost = G[i][j].second;
145                     if(dist[v] == dist[i] + cost)
146                     {
147                         edge.push_back(Edge(i, v, cost));
148                         //sum+=cost;
149                         //cout<<111111<<endl;
150                         //cout<<i<<"	"<<v<<"	"<<sum<<endl;
151                         //break;
152                     }
153                 }
154             ///}
155         }
156        printf("%lld
", Kruskal());
157         //printf("%lld
",sum);
158     }
159     return 0;
160 }