글 읽기 - 1504번 특정한 최단거리찾기 36%에서 틀립니다. 반례좀 찾아주세요

rhkd2612 6년 전 0

long형으로 바꿔도 안되요

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <functional>

using namespace std;

#define MAX 805
#define INF 10000000

int v, e;
int result = INF;
int cost[MAX][MAX];
vector<pair<int, int>> vec[MAX];
int mustGo[2];

int dijkstra(int from, int to)
{
	priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int> >> q;

	q.push(make_pair(0, from));

	for (int i = 0; i <= v; i++)
		cost[from][i] = INF;

	while (!q.empty())
	{
		pair<int, int> p = q.top(); q.pop();

		if (p.second == to)
		{
			if (p.first < cost[from][to])
				cost[from][to] = p.first;

			continue;
		}

		if (cost[from][p.second] <= p.first)
			continue;

		cost[from][p.second] = p.first;

		for (int i = 0; i < vec[p.second].size(); i++)
		{
			int nDirect = vec[p.second][i].first;
			int nDistance = p.first + vec[p.second][i].second;

			if (nDistance < cost[from][i])
				q.push(make_pair(nDistance, nDirect));
		}
	}

	return cost[from][to];
}

int main()
{
	cin >> v >> e;

	for (int i = 0; i < e; i++)
	{
		int from, to, distance;

		scanf("%d %d %d", &from, &to, &distance);
		
		vec[from].push_back(make_pair(to, distance));
		vec[to].push_back(make_pair(from, distance));
	}

	scanf("%d %d", &mustGo[0], &mustGo[1]);

	result = min(result, min(dijkstra(1, mustGo[0]) + dijkstra(mustGo[0], mustGo[1]) + dijkstra(mustGo[1], v), dijkstra(1, mustGo[1]) + dijkstra(mustGo[1], mustGo[0]) + dijkstra(mustGo[0], v)));

	cout << ((result >= INF) ? -1 : result);

	return 0;
}

ehddml3 6년 전 0

5가 나와야하지 않을까요

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
1 3

rhkd2612 6년 전 0

ehddml3

그러면 그래프가

0 3 5 4

3 0 3 5

5 3 0 1

4 5 1 0 인데

1 - 3 - 4 = 5 + 1 = 6이고

그 반대 케이스는 안되지 않나요?

ehddml3 6년 전 1

아.. 제가 잘못봤네용..

대신 코드에서 틀린부분을 찾아왔어요

if (nDistance < cost[from][i])

q.push(make_pair(nDistance, nDirect));

이 부분에서 cost[from][nDirect] 를 cost[from][i]로 쓰셨어요

ㄹ

rhkd2612 6년 전 1

감사합니다 바로통과했어요

ehddml3 6년 전 0

그리구 pq에서 뽑아낸 다음에 cost를 바꾸는건 pq 크기가 더 늘어기 쉬워서 시간이 좀 빡빡하면 시간초과가 날 수 있어요

cost[from][from]=0;
while (!q.empty())
{
pair<int, int> p = q.top(); q.pop();

if (cost[from][p.second] < p.first)
continue;

for (int i = 0; i < vec[p.second].size(); i++)
{
int nDirect = vec[p.second][i].first;
int nDistance = p.first + vec[p.second][i].second;

if (nDistance < cost[from][nDirect]){
q.push(make_pair(nDistance, nDirect));
cost[from][nDirect]=nDistance;
}
}
}

이런식으로 쓰면 더 빨리 돌아갑니다

rhkd2612 6년 전 1

조언 감사합니다

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

문제

문제

출처

ICPC

1504번 특정한 최단거리찾기 36%에서 틀립니다. 반례좀 찾아주세요

rhkd2612 6년 전 0

ehddml3 6년 전 0

rhkd2612 6년 전 0

ehddml3 6년 전 1

rhkd2612 6년 전 1

ehddml3 6년 전 0

rhkd2612 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말