专栏首页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;
}
本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://blog.csdn.net/qq_41603898复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 两个超详细的python爬虫技能树(思维导图)

    在python微信群里说过会分享看过的两个python爬虫技能树(思维导图),这回算是填个坑。

    古柳_DesertsX
  • (42) 排序二叉树 / 计算机程序的思维逻辑

    40节介绍了HashMap,41节介绍了HashSet,它们的共同实现机制是哈希表,一个共同的限制是没有顺序,我们提到,它们都有一个能保持顺序的对应类TreeM...

    swiftma
  • Story 场景树——锻练开发人员 "简单设计" 的思维力

    Story 场景树, 主要是要帮助开发人员, 锻练 “简单设计” 的思维;当经过一段时间的锻练后, 开发人员就可没有 “必要” 的再使用 Story 场景树进行...

    Techeek
  • Story 场景树; 锻练开发人员 “简单设计” 的思维力

    但是, 简单设计假如只是写写文档, 而不能指导开发, 这样的简单设计, 就只是在瞎折腾。

    Ken Fang 方俊贤
  • 【Flink】第十四篇:LSM-Tree一般性总结

    【Flink】第十二篇:记kudu-connector写CDC数据的-D数据时,报主键不存在的异常

    章鱼carl
  • 决策树:一种像人脑一样工作的算法

    决策树是用于机器学习最流行的算法之一,尤其对于分类和回归问题。我们每次做决策时大脑都像决策树一样工作。

    AI研习社
  • 回溯法之装载问题

    先来看装载问题问题背景描述 ? 装载问题可用动态规划解决,但回溯法有时能取得更好的效果 (1)First ship the first ship as muc...

    张俊怡
  • 如何解读决策树和随机森林的内部工作机制?

    选自 Pivotal 机器之心编译 参与:Panda 随机森林在过去几年里得到了蓬勃的发展。它是一种非线性的基于树的模型,往往可以得到准确的结果。但是,随机森林...

    机器之心
  • 拜托,面试别再问我三进制了!!!

    通过这一种关系:1,2,4,8,16就能够表示[0, N]之间的所有数,其中N=1+2+4+8+16=31。

    架构师之路
  • 关于数据治理的读书笔记 - 什么是数据文化?

    都说“数字转型,文化先行”,但做起来,并不容易,“文化”可能很虚,但他的作用,不容忽视。良好的企业文化为员工提供了做选择时的指导方针,有利于企业数字化目标的实现...

    bisal
  • 【算法学习】再谈回溯法

    回溯法,又叫试探法,是一种寻找最优解的暴力搜寻法,也比较容易理解(适合小白学习)。但是,由于暴力,回溯法的时间复杂度较高,因此在比较一些数字较大的问题时,比如上...

    短短的路走走停停
  • 0-1背包-回溯法

    算法描述: 0-1背包的回溯法,与装载问题的回溯法十分相似。在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树中有可能包含最优解时才...

    用户1154259
  • 3分钟速读原著《Java数据结构与算法》(三)

    cwl_java
  • 0-1背包-分支限界

    算法描述:   活结点优先队列中结点元素N的优先级由该结点的上界函数Bound计算出的值uprofit给出。   子集树中以结点N为根的子树中任一结点的价值不超...

    用户1154259
  • leetcode刷题(75)— 547. 朋友圈

    班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋...

    老马的编程之旅
  • Union-Find 并查集算法详解

    今天讲讲 Union-Find 算法,也就是常说的并查集算法,主要是解决图论中「动态连通性」问题的。名词很高端,其实特别好理解,等会解释,另外这个算法的应用都非...

    labuladong
  • 动态规划算法(Dynamic Programming)之0-1背包问题

    前面讲了0-1背包的回溯解决方法,它是穷举所有可能,复杂度是指数级别的,如何降低时间复杂度呢?

    Michael阿明
  • AI入侵机械设计,苦逼的“机械狗”还有未来吗?

    近几年,机械行业的平均薪资一直被 IT 碾压,更不用说 IT 行业里炙手可热的人工智能。现如今,AI 一路攻城略地,已经深入里很多行业和领域,其中就包括制造业,...

    AI科技大本营
  • 决策树算法简单应用

    版权声明:本文为博主原创文章,欢迎转载。 ...

    程裕强

扫码关注腾讯云开发者

领取腾讯云代金券