首页 > 代码库 > [51nod1443]路径和树
[51nod1443]路径和树
给定一幅无向带权连通图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 long10 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 }
[51nod1443]路径和树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。