admin 管理员组

文章数量: 1086866

楚楚街 旅途

题目描述

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

输入描述:
第一行包含两个整数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


/*** 最短路径Dijkstra*/
public class Main {private static void init(int[][] road,int n) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {road[i][j] = Integer.MAX_VALUE;}}}private static int dijkstra(int[][] road,int s,int n,int girl1) {int[] dist = new int[n + 1];boolean[] isVisited = new boolean[n + 1];for (int i = 2; i <= n; i++) {dist[i] = road[s][i];}dist[s] = girl1;isVisited[s] = true;for (int i = 2; i < n; i++) {int minDist = Integer.MAX_VALUE;int v = 1;for (int j = 1; j <= n; j++) {if (!isVisited[j] && dist[j] < minDist) {minDist = dist[j];v = j;}}if (minDist == Integer.MAX_VALUE) {break;}isVisited[v] = true;for (int j = 1; j <= n; j++) {if (!isVisited[j] && road[v][j] < Integer.MAX_VALUE) {int temp = dist[v] + road[v][j];dist[j] = dist[j] < temp ? dist[j] : temp;}}}return dist[n] + girl1;}public static void main(String[] arg){Scanner scan=new Scanner(System.in);while(scan.hasNext()){String[] nm = scan.nextLine().split(" ");int n = Integer.parseInt(nm[0]);int m = Integer.parseInt(nm[1]);int[][] road = new int[n + 1][n + 1];init(road,n);int[] girls = new int[n + 1];String[] girls_in = scan.nextLine().split(" ");for (int i = 1; i <= n; i++) {girls[i] = Integer.parseInt(girls_in[i-1]);}for (int i = 0; i < m; i++) {String[] pq = scan.nextLine().split(" ");int p = Integer.parseInt(pq[0]);int q = Integer.parseInt(pq[1]);road[p][q] = girls[q];road[q][p] = girls[p];}System.out.println(dijkstra(road,1,n,girls[1]));}scan.close();}}

本文标签： 楚楚街 旅途

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