题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1443
首先要得到一个最短路树；
注意边权和最小，因为在最短路中，每个点的 dis 都是固定的，所以边权和最小...
边权和会不同是因为，虽然 dis 固定，但由于组成一棵树，所以有些边被很多点算入 dis ，而它的边权只应被算一次；
发现每个点对直接连向它的那条边的选择是相互独立的，所以直接在那些边中选最小的即可。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; int const xn=3e5+5; int n,m,hd[xn],ct,to[xn<<1],nxt[xn<<1],st; ll dis[xn],ans,w[xn<<1],fa[xn]; bool vis[xn]; struct N{ ll dis; int id; bool operator < (const N &y) const {return dis>y.dis;} }; priority_queue<N>q; void add(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; w[ct]=z; hd[x]=ct;} int rd() { int ret=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=0; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)ret=(ret<<3)+(ret<<1)+ch-‘0‘,ch=getchar(); return ret*f; } void dijkstra() { memset(dis,0x3f,sizeof dis); dis[st]=0; q.push((N){0,st}); while(q.size()) { int x=q.top().id; q.pop(); if(vis[x])continue; vis[x]=1; for(int i=hd[x],u;i;i=nxt[i]) { if(vis[u=to[i]])continue; if(dis[u]>dis[x]+w[i]) { dis[u]=dis[x]+w[i]; fa[u]=w[i]; q.push((N){dis[u],u}); } else if(dis[u]==dis[x]+w[i])fa[u]=min(fa[u],w[i]); } } } int main() { n=rd(); m=rd(); for(int i=1,x,y,z;i<=m;i++) { x=rd(); y=rd(); z=rd(); add(x,y,z); add(y,x,z); } st=rd(); dijkstra(); for(int i=1;i<=n;i++)ans+=fa[i]; printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/Zinn/p/9699465.html