白準格の最短経路(5719)

最短パス

1.ヒント

1)頂点SSSから全頂点までの最短距離を複数の曲線で求めることができる。どの幹線が最短経路に属するかを判断すると、SSSからDDDまでは判断しにくいが、逆に判断しやすい。

2）複数の出口を通して、最短距離起点SSSのタイル状distdistを得ることができる。このとき、到達点Dでは最短経路に属する本線のみに沿って逆行するものとする。幹線(xなら、 D)(x,\ D)(x, D)存在,dist[x]+w(x, D)=dist[D]dist[x] + w(x,\ D) = dist[D]dist[x]+w(x, D)=dist[D](x)が満たされると、 D)(x,\ D)(x, D)は最短経路に属する幹線である。今xxxに移動して、同じ過程を繰り返してください。

3）DDDからSSSに移動した場合、最短経路に属する幹線を削除する場合、DFSまたはBFSを使用して同じ頂点への複数回のアクセスを防止することができる。

2.近接

後ろから質問してもいいですか?

到着点DDDでSSSに逆行しながら最短経路に属する幹線を見つける.この過程でdist[u]+w(u, v)=dist[v]dist[u] + w(u,\v) = dist[v]dist[u]+w(u, v)=dist[v]が満たされるとuuからvvまでの最短距離はw(u, v)w(u,\v)w(u, vなので幹線(u、 v)(u,\v)(u, v)最短経路に属する.

3.実施

反転幹線をより容易に見つけるために,多出口の時間的複雑さを増大させるため,隣接行列で図形を実現すべきかどうかを考慮したので,反転幹線を格納する図形adj 2を単独で実現した.
削除幹線は隣接行列のbooleanboolean配列を使用します.これにより、マルチセグメントコードを回収できます.

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	// 인접 리스트 방식으로 간선을 저장
	static ArrayList<ArrayList<Pair>> adj;
	// 기존의 간선들을 거꾸로 저장해 놓은 간선
	static ArrayList<ArrayList<Pair>> adj2;
	// 어떤 간선이 삭제되었는지 여부를 저장
	static boolean[][] removed;
	
	static final int INF = 987654321;
	
	// start정점에서 모든 정점으로의 최단거리를 저장한 dist[] 반환
	static int[] dijkstra(int start) {
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		pq.offer(new Pair(start, 0));
		int[] dist = new int[N];
		Arrays.fill(dist, INF);
		dist[start] = 0;
		while (!pq.isEmpty()) {
			Pair p = pq.poll();
			int here = p.num; int cost = p.cost;
			if (dist[here] < cost) continue;
			// 인접한 정점 중 삭제되지 않은 간선만 검사한다
			for (Pair edge : adj.get(here)) if (!removed[here][edge.num]) {
				int there = edge.num;
				int nextCost = cost + edge.cost;
				if (dist[there] > nextCost) {
					dist[there] = nextCost;
					pq.offer(new Pair(there, nextCost));
				}
			}
		}
		return dist;
	}
	
	// start에서 역방향 간선을 찾아가면서 최단경로에 속하는 간선을 지운다
	// 같은 정점을 여러번 방문하는 것을 막기 위해 BFS사용
	static void bfs(int[] dist, int start) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		boolean[] booked = new boolean[N];
		booked[start] = true;
		while (!q.isEmpty()) {
			int here = q.poll();
			for (Pair edge : adj2.get(here)) {
				int there = edge.num; int weight = edge.cost;
				// 조건을 만족하면 there정점에서 here로 오는 경로는 최단경로에 속한다
				// there이 이미 방문한 정점이더라도 edge(here, there)을 검사한다
				if (dist[there] + weight == dist[here]) {
					if (!booked[there]) {
						q.offer(there);
						booked[there] = true;
					}
					// 현재 역방향 간선을 탐색중이므로 edge(there, here)이 제거됨
					removed[there][here] = true;
				}
			}
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		while (true) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			if (N == 0 && M == 0) break;
			st = new StringTokenizer(br.readLine(), " ");
			int S = Integer.parseInt(st.nextToken());
			int D = Integer.parseInt(st.nextToken());
			adj = new ArrayList<>(N); adj2 = new ArrayList<>(N);
			for (int i = 0; i < N; i++) {
				adj.add(new ArrayList<>());
				adj2.add(new ArrayList<>());
			}
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				int p = Integer.parseInt(st.nextToken());
				adj.get(u).add(new Pair(v, p));
				// 역추적할 때 사용할 수 있도록 반대로도 넣어 놓는다
				adj2.get(v).add(new Pair(u, p));
			}
			removed = new boolean[N][N];
			bfs(dijkstra(S), D);
			int ret = dijkstra(S)[D];
			bw.append(ret == INF ? -1 : ret).append("\n");
		}
		System.out.print(bw);
	}
	
}

class Pair implements Comparable<Pair> {
	int num, cost;

	Pair(int t, int w) { num = t; cost = w; }
	
	@Override
	public int compareTo(Pair o) { return cost - o.cost; }
	
}

1）時間複雑度

2）テストケース

6 8
0 5
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
0 2 2
2 5 10
0 5 5
->-1

これは似たようなグラフです.赤い線で表記されているのは最短経路です.最短経路の長さは555であることがわかりやすい.また、最短経路を全て削除すると、000番幹線から取り出せないので、-1に戻らなければなりません.しかし、逆トラッキング時に削除幹線のBFSを誤って記述すると、最短経路の長さはほぼ555となる.

// 조건을 만족하면 there정점에서 here로 오는 경로는 최단경로에 속한다
if (dist[there] + weight == dist[here] && !booked[there]) {
	q.offer(there);
	booked[there] = true;
	// 현재 역방향 간선을 탐색중이므로 edge(there, here)이 제거됨
	removed[there][here] = true;
}

これは私がエラーコードを書いた例です.条件文の!予約に注意してください.通常、BFSの隣接する頂点をチェックする場合は、未アクセスの頂点(または予定されていないアクセス)のみをチェックします.この問題では、隣接する頂点が確定した頂点であっても、最短経路に属する幹線をチェックするので、幹線はすべてチェックしなければなりません.

// 조건을 만족하면 there정점에서 here로 오는 경로는 최단경로에 속한다
// there이 이미 방문한 정점이더라도 edge(here, there)을 검사한다
if (dist[there] + weight == dist[here]) {
	if (!booked[there]) {
		q.offer(there);
		booked[there] = true;
	}
	// 현재 역방향 간선을 탐색중이므로 edge(there, here)이 제거됨
	removed[there][here] = true;
}

このように交換すべきでしょう.