2021 KAO BLIND RECRUITMENT-乗り合わせタクシー料金

using Java 11
「タクシー料金の精算」の確認

import java.io.*;
import java.util.*;
public class Solution {
	public static ArrayList<ArrayList<Node>> map = new ArrayList<>();
	public static boolean[] visited;
	public static int[] fare;
	public static class Node implements Comparable<Node>{
		int to;
		int fare;
		public Node(int to, int fare) {
			this.to = to;
			this.fare = fare;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.fare- o.fare;
		}
	}
	public static int getFare(int start, int s, int a, int b) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(start, 0));
		fare[start] = 0;
		while(!pq.isEmpty()) {
			Node curNode = pq.poll();
			int next = curNode.to;
			if(!visited[next]) {
				visited[next] =  true;
				ArrayList<Node> arr = map.get(next);
				for(int i = 0; i < arr.size(); i++) {
					Node tmp = arr.get(i);
					if(fare[tmp.to] > tmp.fare + fare[next]) {
						fare[tmp.to] = tmp.fare + fare[next];
						pq.add(new Node(tmp.to, fare[tmp.to]));
					}
				}
				
			}
		}
		return fare[s] + fare[a] + fare[b];
	}
	public static int solution(int n, int s, int a, int b, int[][] fares) {
		for(int i = 0; i <= n; i++) {
			map.add(new ArrayList<>());
		}
		for(int i = 0; i < fares.length; i++) {
			map.get(fares[i][0]).add(new Node(fares[i][1], fares[i][2]));
			map.get(fares[i][1]).add(new Node(fares[i][0], fares[i][2]));
		}
		int min = Integer.MAX_VALUE;
		for(int i = 1; i <= n; i++) {
			visited = new boolean[n+1];
			Arrays.fill(visited, false);
			fare = new int[n+1];
			Arrays.fill(fare, 1000001);
			int result = getFare(i, s, a, b);
			if(result < min) min = result;
		}
		return min;
	}
}

📍 複数使用
まずアイデアを出すのはちょっと難しいです.
中間点を通過する最短経路問題は一般に2回のExpostで解決されるため,同様の方法で解決しようとするが,事実はそうではない.(似てるけど)
初めて思いついた方法
中間点(合乗セグメント)をノードmと呼ぶ
s->m,m->a,m->bの最短パスを見つけます.
mの範囲は1<=m<=nであるため、3*n回のマルチタスクを実行しなければならない.
見るからに効率テストは通らないと思います.また,効率的なタイムアウト現象も相次いでいる.ほほほ、だから私はいくつかのグーグルゲームをしました.
ダエストラで計算するとタイムアウトになるのでフロイド外シャーロット主義で解決・・・うん、でも変な頑固さなのか分からないし、Extraで解決したい.だから長い間考えていたアイデア
††逆に考えましょう
問題を見直したところ、与えられた地図は無方向図なので、料金は双方向です.ここには意図があるかもしれないと思うので、逆探索の方法を考えました.
出発地を中間点mとし,最短経路を求め,m->s,m->a,m->b最短経路を一度に求める.
この3つを合わせるといいです(料金はs->mと同じですから!)
共乗しない場合はm=sで解くので,すべての条件を調べることができる.
すなわち、始点1からnまで、n回の最短経路を求める場合は、dist[s]+dist[a]+dist[b]の値を返し、最小値を求めればよい.コードでは、チケットの手配はdistの手配に相当します.

int min = Integer.MAX_VALUE;
for(int i = 1; i <= n; i++) {
	visited = new boolean[n+1];
	Arrays.fill(visited, false);
	fare = new int[n+1];
	Arrays.fill(fare, 1000001);
	int result = getFare(i, s, a, b);
	if(result < min) min = result;
}

📍 ディスクアレイの初期化
そう思ってやっと解けたのに、タイムアウト!(怒っています.)効率テスト用例7は1つ、、、、原因が分からないので、撮って修正して回って、正解だと言いました.😱 🥶 驚きと恐怖の瞬間だった.
他の質問に答えるときは、初めてInteger MAXVALUEで中間点のあるマルチアウトレットdist配列を埋めたときにオーバーフローが発生したことを覚えておいてください.(複数の結果が追加された場合)
そのため、最初は適当な数の「10000001」に設定します.結果効率は7回を超えた.普通に溢れたらタイムアウトじゃなくて失敗
数字が大きすぎて演算速度に影響するとは思わなかったが、そのまま撮るわけにはいかず、初値を「1000001」に変更して通過した.⁉️
それでたくさんの値段が変わりました
100,001 ❌
1,000,001 ⭕️
10000001❌(7回の効率テストに失敗)
10000001❌(効率テスト7回のみ失敗)
Integer.MAX_VALUE/3 - 1 ⭕️
:715827881ぐらいですが、fare[s]+fare[a]+fare[b]の計算値をオーバーフローさせたくなければ、この値でいいです.
一定値以上でタイムアウトが続くと理解しますが、うーん...
グーグルゲームをやってみても、説明する人はいません.(知っている方はコメントをお願いします)初期値を設定すると効率テストに影響しますが、一定の範囲内ではできないので、アルゴリズムを間違えるかもしれません.