PTA旅游规划(JAVA)

题目大意

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:

输入说明：输入数据的第 1 行给出 4 个正整数 n、m、s、d，其中 n（2≤n≤500）是城市的个数，顺便假设城市的编号为 0~(n−1)；m 是高速公路的条数；s 是出发地的城市编号；d 是目的地的城市编号。随后的 m 行中，每行给出一条高速公路的信息，分别是：城市 1、城市 2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过 500。输入保证解的存在。

输出格式:

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出样例:

3 40

java代码解决

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Math.max;
import static java.lang.Math.min;

public class Main {
    static int[][] g = new int[509][509];
    static int[][] expense = new int[509][509];
    static int[] dist = new int[509];
    static int[] cost = new int[509];
    static PriorityQueue<pair> pq = new PriorityQueue<>();
    static int n,m,s,d;
    static boolean[] vis = new boolean[509];

    public static class pair implements Comparable<pair> {
        int x, y;
        public pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(pair o) {
            return this.y - o.y;
        }
    }

    public static void dijkstra() {
        for(int i=0;i<n;i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        for(int i=0;i<n;i++) {
            cost[i] = Integer.MAX_VALUE;
        }
        dist[s] = 0;
        cost[s] = 0;
        pq.add(new pair(s,dist[s]));
        while(!pq.isEmpty()) {
            pair p = pq.poll();

            if(vis[p.x]) continue;
            vis[p.x] = true;

            for(int i=0;i<n;i++) {
                if(vis[i]) continue;
                if(g[p.x][i] != -1 && dist[i] > dist[p.x] + g[p.x][i]) {
                    dist[i] = dist[p.x] + g[p.x][i];
                    cost[i] = cost[p.x] + expense[p.x][i];
                    pq.add(new pair(i,dist[i]));
                }
                if(g[p.x][i] != -1 && dist[i] == dist[p.x] + g[p.x][i]) {
                    cost[i] = min(cost[p.x] + expense[p.x][i],cost[i]);
                }
            }
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) {
        FastReader scanner = new FastReader();
        n = scanner.nextInt();
        m = scanner.nextInt();
        s = scanner.nextInt();
        d = scanner.nextInt();
        for(int i=0;i<509;i++) {
            for(int j=0;j<509;j++) {
                g[i][j] = -1;
                expense[i][j] = -1;
            }
        }
        for(int i=0;i<m;i++) {
            int u = scanner.nextInt();
            int w = scanner.nextInt();
            int dis = scanner.nextInt();
            int e = scanner.nextInt();
            g[u][w] = dis;
            g[w][u] = dis;
            expense[u][w] = e;
            expense[w][u] = e;
        }
        dijkstra();
        System.out.print(dist[d] + " ");
        System.out.print(cost[d]);
    }
}

大致思路

本题涉及双权值最短路问题，用了优先队列优化，但是由于用的是邻接矩阵，所以如果n再大些可能就无法通过，最好改成邻接表。

在此题中，有可能多个路径长度一样，要选择收费最低的，这就是多权值的体现，为了解决这个问题，我们会在路径长度需要更新的时候修改最小花费，注意是修改不是更新，因为遇到路径更短的情况时不论前一个收费多低或者多高，都是不可取的，核心代码如下

if(g[p.x][i] != -1 && dist[i] > dist[p.x] + g[p.x][i]) {
                dist[i] = dist[p.x] + g[p.x][i];
                cost[i] = cost[p.x] + expense[p.x][i];
                pq.add(new pair(i,dist[i]));
            }
            if(g[p.x][i] != -1 && dist[i] == dist[p.x] + g[p.x][i]) {
                cost[i] = min(cost[p.x] + expense[p.x][i],cost[i]);
            }

那么如果是cpp代码本题就到此为止了，但是关键在于java代码输入很慢，也因此卡了我一段时间

输入优化

我们在Main类中定义快速输入

static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }

并且将Scanner换成FasterReader即可

至此，本题在完全图的情况下也能控制在800ms以内，完结撒花🎉🎉🎉