admin 管理员组

文章数量: 1086866

算法题：旅途（楚楚街2016招聘笔试）

名企笔试：楚楚街2016招聘笔试（旅途）
题目描述

原来是要到醋溜站台乘坐醋溜快车到醋溜港”，亮亮解出了地图隐藏的秘密，赶紧奔向醋溜站台，但到了之后，亮亮忧桑地发现，从醋溜站台到醋溜港沿途的每个车站都有很多美女被他飒爽的英姿所吸引，只要经过车站就会被这些漂亮的女孩搭讪，但是现在亮亮一心想要寻找楚楚街而没空去搭理她们，所以亮亮希望在抵达醋溜港的时候被搭讪的次数最少。问亮亮抵达醋溜港最少会被搭讪多少次？

输入描述:

第一行包含两个整数N(2<=N<=5000),M(1<=M<=50000)。N表示公有N个汽车站，M表示公有M条公路，起点为1，终点为N。
第二行包含N个整数(0<=K<=10000)，第i个整数表示在第i站有K个美女想要搭讪亮亮。
接下来M行，每行包含两个整数P(1<=P<=N),Q(1<=Q<=N),代表P,Q两个站是有班车直达的。

输出描述:

一个整数，即亮亮抵达醋溜港最少需要被搭讪的次数。

输入例子:

5 5
0 1 1 3 6
1 2
1 4
2 3
3 5
4 5

输出例子:

8


java版本的代码实现：

package cn.cat.algorithm;public class Journey {/*** 分析：使用贪婪算法，假设所有起点1线路最后都可以达到终点，*      一边寻找线路点，一边计算搭讪次数，如果最终真的能达到终点，则统计的搭讪次数有效，*      比较所有有效的搭讪数，获得最小值。* * @Description: * @author gwj* @Created 2018年4月18日 下午3:17:49 * @param args*/public static void main(String[] args) {//终点，线路数int n=5, m=5;//搭讪数据int[] accosts = new int[]{0, 1, 1, 3, 6};//线路数据int[][] lines = new int[][]{new int[]{1, 2},new int[]{1, 4},new int[]{2, 3},new int[]{3, 5},new int[]{4, 5}};int minAccostCount = Integer.MAX_VALUE;for (int i = 0; i < m; i++) {//找到起点站if (lines[i][0] == 1) {int curStation = lines[i][1];//注意数组下标从0开始，获取站点的搭讪数=站点-1int accostCount = accosts[lines[i][0] - 1] + accosts[lines[i][1] - 1];for (int j = 0; j < lines.length; j++) {if (lines[j][0] == curStation) {curStation = lines[j][1];accostCount += accosts[curStation -1];}if (curStation == n) {break;}}//lines[i][0]起点能到达终点，则比较并获取最小搭讪数if (curStation == n && minAccostCount > accostCount) {minAccostCount = accostCount;}}}System.out.println(minAccostCount);}
}

本文标签： 算法题旅途（楚楚街2016招聘笔试）

版权声明：本文标题：算法题：旅途（楚楚街2016招聘笔试） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1693758684a241130.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。