글 읽기 - 왜 시간초과 인지 잘 모르겠습니다.

cocoroco 5년 전 0

안녕하세요. 왜 시간초과인지 잘 모르겠습니다.

문제 풀이 방법은 이렇습니다.

모든 도시 사이의 가중치를 저장합니다. 두 지점이 특별한 도시라면 텔레포트 한 가중치 T와 멘하탄 거리를 비교해 작은 값을 넣습니다.
M 번 다익스트라 알고리즘을 통해 최단거리를 찾습니다.
출력합니다.

가중치를 저장하는데 약 (1000*999)/2

다익스트라 를 M번 돌려 M * NlongN 시간복잡도로 최단거리를 구합니다.

즉 M,N <=1000 이므로 1000* 1000log1000 이라서

2초안에는 무조건 돌거 같은데 왜 시간초과인지 모르겠습니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;

typedef struct city {
	int x; int y;
	int id;
};
city C[1001];
int adj[1001][1001];
int dist[1001];
int N, T;

void dji(int S, int E) {
	priority_queue <pair<int, int > > pq;
	pq.push({ 0,S });

	while (!pq.empty()) {
		int w = -pq.top().first;
		int here = pq.top().second;

		pq.pop();
		if (dist[here] != -1) continue;

		dist[here] = w;
		if (here == E) {
			return;
		}
		for (int i = 1; i <= N; i++) {
			if (adj[here][i] == -1) continue;
			if (dist[i] != -1) continue;

			pq.push({ -w - adj[here][i], i });
		}
	}
}
int main() {
	scanf("%d %d", &N, &T);

	for (int i = 1; i <= N; i++) {
		scanf("%d %d %d", &C[i].id, &C[i].x, &C[i].y);
	}

	memset(adj, -1, sizeof(adj));

	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			int temp = abs(C[i].x - C[j].x) + abs(C[i].y - C[j].y);
			if (C[i].id == 1 && C[j].id == 1) {
				if (temp < T) {
					adj[i][j] = temp; adj[j][i] = temp;
				}
				else {
					adj[i][j] = T; adj[j][i] = T;
				}
			}
			else {
				adj[i][j] = temp; adj[j][i] = temp;
			}
		}
	}

	int M; scanf("%d", &M); int a, b;
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		memset(dist, -1, sizeof(dist));
		dji(a, b);
		printf("%d\n", dist[b]);
	}
	return 0;
}

chogahui05 5년 전 0

모든 도시의 가중치를 저장합니다.

E = n^2

V = n

다익스트라 1번 돌 때 복잡도가 ElogV라면 m번 돌면 mElogV 아닌가요?

cocoroco 5년 전 0

아 그렇군요 제가 시간복잡도를 ElogN 말고 NlogN으로 계산하고 있었네요.

혹시 이문제 그럼 다익스트라로 풀지 못하는 건가요??

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 시간초과 인지 잘 모르겠습니다.

cocoroco 5년 전 0

chogahui05 5년 전 0

cocoroco 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말