그래프의 모든 임의의 v1, v2에 대해 최단거리를 구해주는 알고리즘

알고리즘 템플릿

void floyd() {
	// dist 배열 초기화. min() 함수로 값을 최적화하기 때문에 반드시 INF로 초기화 해줄 것
	fill(*(dist), *(dist + N + 1), INF);

	// 나 자신은 항상 0
	for (int i = 1; i <= N; ++i)
		dist[i][i] = 0;

	// 주어진 간선 정보로 직접 연결된 dist[s][e], dist[e][s] 갱신
	for (int i = 0; i < M; ++i) {
		int s = edges[i].start;
		int e = edges[i].end;
		int len = edges[i].length;

		if (dist[s][e] > len) {
			dist[s][e] = len;
			dist[e][s] = len;
		}
	}

	// Floyd-Warshall 알고리즘
	for (int k = 1; k <= N; ++k)
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= N; ++j)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

문제 및 풀이

Ignition (https://www.acmicpc.net/problem/13141)

모든 노드 간 최단거리를 우선 구한 뒤, 최대 최단거리 + edge가 타들어가는 시간을 구해 답을 도출

합승 택시 요금 (Link)

노드의 개수가 200개 이내로 작고 그래프에서 최단거리를 구한다면 플로이드 워셜을 먼저 생각하자.