글 읽기 - 1504 Timeout

midinpa 4년 전 0

다익스트라 3번 돌렸는데요

9%에서 시간초과가 납니다 ㅠ

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

constexpr int INF = 987654321;
int cost[800][800];
int dist[3][800];
int n;


struct cmp
{
	bool operator()(pair<int, int> a, pair<int, int> b)
	{
		return a.first < b.first;
	}
};


void dijkstra(int k, int start) {
	for (int i = 0; i < n; i++) {
		dist[k][i] = INF;
	}

	priority_queue <pair<int, int>, vector<pair<int, int>>, cmp> pq;

	pq.push(make_pair(0, start));
	dist[k][start] = 0;
	while (!pq.empty()) {
		int c = pq.top().first;
		int node = pq.top().second;
		pq.pop();
		if (c > dist[k][node]) continue;

		for (int i = 0; i < n; i++) {
			if (cost[node][i] > 0) {
				if (c + cost[node][i] < dist[k][i]) {
					dist[k][i] = c + cost[node][i];
					pq.push(make_pair(c + cost[node][i], i));
				}
			}
		}
	}
}

int main() {

	int m;
	int bypass1, bypass2;

	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cost[i][j] = -1;
		}
	}

	int a, b, c;
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		if (cost[a - 1][b - 1] < 0) {
			cost[a - 1][b - 1] = c;
			cost[b - 1][a - 1] = c;
		}
		else if (cost[a - 1][b - 1] > c) {
			cost[a - 1][b - 1] = c;
			cost[b - 1][a - 1] = c;
		}
	}

	scanf("%d %d", &bypass1, &bypass2);

	dijkstra(0, 0);
	dijkstra(1, bypass1 - 1);
	dijkstra(2, bypass2 - 1);

	int min = dist[0][bypass1 - 1] + dist[1][bypass2 - 1] + dist[2][n - 1];
	if (min > dist[0][bypass2 - 1] + dist[2][bypass1 - 1] + dist[2][n - 1]) min = dist[0][bypass2 - 1] + dist[2][bypass1 - 1] + dist[2][n - 1];
	if (min >= INF) min = -1;

	printf("%d", min);

	return 0;
}

djm03178 4년 전 2

1. priority_queue는 큰 원소부터 빼내므로 operator() 내의 연산자의 방향이 뒤집혀야 합니다.

2. 81번째 줄에서 dist[2][n - 1] 2개는 모두 dist[1][n - 1]로 바뀌어야 합니다.

3. INF가 너무 커서 세 개를 더하면 int의 범위를 벗어납니다. 더 줄여야 합니다.

midinpa 4년 전 0

감사합니다.

근데 '틀렸습니다'로 바꼈네요 ㅠ

midinpa 4년 전 0

1. priority_queue는 큰 원소부터 빼내므로 operator() 내의 연산자의 방향이 뒤집혀야 합니다.

이걸 해줬더니 틀렸다네요.. 뭔가 근본적으로 문제가 있나봐요

djm03178 4년 전 0

제가 저거 3개만 고쳐서 내봤는데 맞았습니다. 제대로 처리했는지 다시 확인해 보세요.

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

문제

문제

출처

ICPC

1504 Timeout

midinpa 4년 전 0

djm03178 4년 전 2

midinpa 4년 전 0

midinpa 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말