PAT条条大路通罗马

简介: 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.

题目描述



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;
    }
  }
} 
目录
打赏
0
0
0
0
16
分享
相关文章
|
6月前
|
什么是 PagingAndSortingRepository?
【8月更文挑战第21天】
153 0
JPA中@ElementCollection使用
JPA中@ElementCollection使用
92 0
ApacheHudi使用问题汇总(一)
ApacheHudi使用问题汇总(一)
75 0
parameterType是必须写的吗?
xml中没有配置parameterType,但是这是正确的,因为mybatis能自动识别,但返回值类型不能不写,因为mybatis需要将获得结果封装到相应的类中,查询的字段与类的属性需要一致。
460 0
parameterType是必须写的吗?
cclientX,pageX,screenX等详解
clientX 观点:鼠标相对于WINDOWS的坐标。 这里这个WINDOWS是指我们能看见的浏览器大小。所以不可能超过显示器的大小,如 screen.width,screen.height
138 0
Pangram
Pangram
138 0
Pangram
PAT有几个pat
字符串APPAPT中包含了两个单词“PAT”,其中第一个PAT是第2位§,第4位(A),第6位(T);第二个PAT是第3位§,第4位(A),第6位(T)。 现给定字符串,问一共可以形成多少个PAT?
156 0
你真的了解RPA吗?
RPA(Robotic Process Automation),译为机器人流程自动化,也可称为数字化劳动力(Digital Labor),是一种智能化软件,它可以像人类一样,通过简单的编程来完成设定好的任务流程,优化整个企业的基础流程作业,降低成本、提高效率。
2161 0
PathAnimation
原文:PathAnimation 使用Blend制作PathAnimation 1:选中Path转换为运动路径 2:选择目标对象   PathAnimation使用动态的Path PathAnimation动画在播放的时候,PahtGeometry是已经确定的,不会改变,不会实时的根据Pa...
920 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等