腾讯2018校招软件开发在线笔试-编程题一

发表于 | 分类于 ，

题目

描述

给定一个 n 阶无向完全图,求第 1 个节点到第 2 个节点的最短距离,
其中可以把 k 条边的距离减半

输入

第 1 行 n,k ,n-节点个数,k-可减半的边的条数
2 到 n+1 行,包含 n 个 0-9 数字的字符串,为第 i 个节点到各个节点的距离
对于所有合法的 i ,dis[i][i]=0;

输出

1 行,最短路径

Example

Input

Output

题解

深度优先搜索

  • 无负权值,两点之间最短距离,Dijkstra算法,这是看到这个题的想法,然而,不对!
  • 用 stack 记录路径,同时用 set 记录路径权值 , ksum 记录前 k 大权值和,sum 记录全路径权值和,
  • 深搜全部路径,求出最小值
1
2