给定一幅无向带权连通图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
输出这棵树的最小的权值之和。
不能直接求完最短路图后跑MST。。因为最短路图的边都是有向的。答案应该是最短路图里每个点最小的前驱边之和。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<cmath> 7 #define ll long long 8 #define ui unsigned int 9 #define ull unsigned long long 10 using namespace std; 11 const int maxn=300233; 12 struct zs{int too,pre,dis;}e[maxn<<1];int tot,last[maxn]; 13 int dl[10023333],pre[maxn]; 14 ll dis[maxn],ans; 15 int i,j,k,n,m; 16 bool u[maxn]; 17 18 int ra,fh;char rx; 19 inline int read(){ 20 rx=getchar(),ra=0,fh=1; 21 while((rx<‘0‘||rx>‘9‘)&&rx!=‘-‘)rx=getchar(); 22 if(rx==‘-‘)fh=-1,rx=getchar(); 23 while(rx>=‘0‘&&rx<=‘9‘)ra*=10,ra+=rx-48,rx=getchar();return ra*fh; 24 } 25 26 27 inline void insert(int a,int b,int c){ 28 e[++tot].too=b,e[tot].dis=c,e[tot].pre=last[a],last[a]=tot, 29 e[++tot].too=a,e[tot].dis=c,e[tot].pre=last[b],last[b]=tot; 30 } 31 inline void spfa(int s){ 32 memset(dis+1,60,n<<3); 33 int l=0,r=1,i,now,to;dl[1]=s,dis[s]=0; 34 while(l<r)for(now=dl[++l],u[now]=0,i=last[now];i;i=e[i].pre) 35 if(dis[to=e[i].too]>dis[now]+e[i].dis){ 36 dis[to]=dis[now]+e[i].dis,pre[to]=e[i].dis; 37 if(!u[to])dl[++r]=to,u[to]=1; 38 }else if(dis[to]==dis[now]+e[i].dis&&e[i].dis<pre[to])pre[to]=e[i].dis; 39 } 40 int main(){ 41 n=read(),m=read(); 42 for(i=1;i<=m;i++)j=read(),k=read(),insert(j,k,read()); 43 int s=read();spfa(s); 44 for(i=1;i<=n;i++)ans+=pre[i]; 45 printf("%lld\n",ans); 46 }
原文：http://www.cnblogs.com/czllgzmzl/p/5946664.html
