专栏首页wymP1268 树的重量 思维

P1268 树的重量 思维

题意: 告诉图中任意两点最短路,求所有路之和。

显然

#include <bits/stdc++.h>
using namespace std;
int dis[35][35];
int main()
{
	int n;
	while(scanf("%d",&n)&&n){
		for(int i=1;i<=n-1;i++){
			for(int j=i+1;j<=n;j++){
				scanf("%d",&dis[i][j]);
			}
		}
		int ans = dis[1][2];
		int tmp;
		for(int i=3;i<=n;i++){
			tmp = 0x7fffffff;
			for(int j=1;j<i;j++){
				tmp = min(tmp, (dis[1][i]+dis[j][i] - dis[1][j])/2 );
			}
			ans+=tmp;
		}
		printf("%d\n",ans);	
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • RMQ——模板

     RMQ(rang minimun/maximun query,区间最佳查询)的主要思想是动态规划。

    用户2965768
  • E旅行商问题

     从1走遍所有点,则必定会重复走很多路,选择从一到最远的一条路只走一边,其他全都要走两遍。

    用户2965768
  • HDU 6629 (2019杭电第五场 1006) string matching (扩展kmp)

    题意: 求字符串 s[i…len−1] and s[0…len−1] i>0 最长公共前缀长度求解过程的比较次数

    用户2965768
  • RMQ——模板

     RMQ(rang minimun/maximun query,区间最佳查询)的主要思想是动态规划。

    用户2965768
  • 浅谈我对动态规划的一点理解---大家准备好小板凳,我要开始吹牛皮了~~~

    前言 作为一个退役狗跟大家扯这些东西,感觉确实有点。。。但是,针对网上没有一篇文章能够很详细的把动态规划问题说明的很清楚,我决定还是拿出我的全部家当,来跟大家分...

    Angel_Kitty
  • cf1042F. Leaf Sets(贪心)

    考场上想的贪心是对的:考虑一棵子树,如果该子树内最深的两个节点的距离相加$>k$就删掉最深的那个点,向上update的时候只返回最深的点的深度

    attack
  • Codeforces 977D 题解报告

    http://codeforces.com/contest/977/problem/D

    海天一树
  • 【CCCC天梯赛决赛】

    cccc的天梯赛决赛,水题一样的水,中档题以上的还是没做出来。补了一下题,觉得其实也不是很难,主要是练的少。

    饶文津
  • 挑战程序竞赛系列(3):2.3需要思考的动规

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • UVA-11600-Masud Rana

    ACM模版 描述 ? ? 题解 image.png ? 保存六位小数…… 代码 #include <cstdio> #include <cstring> #in...

    f_zyj

扫码关注云+社区

领取腾讯云代金券