题目描述
Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.
输入描述:
Each input file contains one test case. For each case, the first line contains 2 positive integers N (2<=N<=200), the number of cities, and K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N-1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format “City1 City2 Cost”. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome.
输出描述:
For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommended. If such a route is still not unique, then we output the one with the maximum average happiness – it is guaranteed by the judge that such a solution exists and is unique.
Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommended route. Then in the next line, you are supposed to print the route in the format “City1->City2->…->ROM”.
输入例子:
6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1
输出例子:
3 3 195 97
HZH->PRS->ROM
大体意思就是先输入城市数量，道路数量，起点城市，然后输入城市名和城市和幸福感，在输入可以连接的城市。要求你按要求输出最短路径的那个过程（如果路径相同，包含其他比较）。
这是一道求最短路径问题，算法核心是dijster算法。首先在输入时候用两个map实现转换。
一个二维数组储存联通花费。一个一维数组储存最小值（该点），一个集合（或者boolean数组）记录该点是否被确定。将要计算的点放入优先队列中。这样每次抛出cost最小的点，那么每次抛出的点的距离就可以确定，
代码如下：
package 甲; import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; public class pat02 { static int allcan=0;//所有能过 static int happy=0; static int mincost=Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc=new Scanner(System.in); Map<String,Integer> map1=new HashMap(); Map<Integer,String> map2=new HashMap(); int a=sc.nextInt();//城市数 int b=sc.nextInt();//马路数量 String from=sc.next();//初始地 int happ[]=new int [a];//记录happy值 map1.put(from, 0);//根据中文找字母 map2.put(0, from);//根据字母找英文 int bool[][]=new int[a][a];//计算长度 for(int i=1;i<a;i++) { String name=sc.next(); int happy1=sc.nextInt(); happ[i]=happy1; map1.put(name, i); map2.put(i, name); } for(int i=0;i<b;i++) { String name1=sc.next(); String name2=sc.next(); int mapget=sc.nextInt(); bool[map1.get(name1)][map1.get(name2)]=mapget;//城市联通花费 bool[map1.get(name2)][map1.get(name1)]=mapget; } int last=map1.get("ROM");//截至地址 int judgel[]=new int [a];//记录点的cost花费 for(int i=0;i<a;i++) { judgel[i]=Integer.MAX_VALUE; } List list=new ArrayList(); Queue<place> q1=new PriorityQueue(compare); place first=new place(0,0,0,0); place finalplace=new place(0,0,0,0);//最终的解 q1.add(first); //list.add(first); while(!q1.isEmpty()) { place p1=q1.poll(); list.add(p1.name); if(p1.name==last) { if(mincost>p1.cost) {allcan=1;mincost=p1.cost;happy=p1.happy;finalplace=p1;} else if(mincost==p1.cost) {allcan++;if(happy<p1.happy) {finalplace=p1;happy=p1.happy;} else if(happy==p1.happy) {if(finalplace.number>p1.number)finalplace=p1;}} } else if(p1.cost>mincost) {} else for(int i=0;i<a;i++) { if(bool[p1.name][i]>0&&!list.contains(i))//这个点还未被确定 { int teamp[]=p1.allname.clone(); teamp[p1.number+1]=i; q1.add(new place(i,p1.cost+bool[p1.name][i],p1.happy+happ[i],p1.number+1,teamp)); if(judgel[i]>p1.cost+bool[p1.name][i]) { judgel[i]=p1.cost+bool[p1.name][i]; } } } } System.out.println(allcan+" "+ mincost+" "+happy+" "+happy/(finalplace.number)); int teamp[]=finalplace.allname; for(int i=0;i<finalplace.number+1;i++) { if(i==finalplace.number) {System.out.print(map2.get(teamp[i]));} else System.out.print(map2.get(teamp[i])+"->"); } } static Comparator<place> compare=new Comparator<place>() { @Override public int compare(place o1, place o2) { return (o1.cost-o2.cost); } }; static class place { int name;//对应的数字 int cost;//花费 int happy;//满意度 int number;//走过的数量 int allname[]=new int[202];//用于记录走过路径，使用时候和number配合使用 public place() { } public place(int name) { this.name=name; } public place(int name,int cost,int happy,int number) { this.name=name;this.cost=cost;this.happy=happy;this.number=number; } public place(int name,int cost,int happy,int number,int allname[]) { this.name=name;this.cost=cost;this.happy=happy;this.number=number;this.allname=allname; } } }
