글 읽기 - 90%에서 틀립니다.

DryType 6년 전 0

1에서 각 노드의 최단경로,

p1에서 각 노드의 최단경로,

p2에서 각 노드의 최단경로를 구해서

만약 (1->p1, 1->p2, 1->N) 세가지가 모두 갈수있는 경로일때

MIN( 1->p1->p2->N, 1->p2->p1->N) 값을 출력하게 했습니다.

90%에서 WA가 되는데 반례가 생각이 안납니다 ㅠㅠ 조언 부탁드리겠습니다.

#include <cstdio>
#include <vector>
#include <queue>
#define FOR(i,n) for(int i=0; i<n ; i++)
#define mp make_pair
#define MIN(a,b) ( (a)<(b)?(a):(b) )

using namespace std;

int dist[801];
int N, E, p1, p2;
bool visit[801];
const int INF = 987654321;
vector<pair<int, int> > node[801];

void dijkstra()
{
	priority_queue<pair<int, int> > pq;
	FOR(i, N+1) dist[i] = INF;
	FOR(i, N+1) visit[i] = false;
	pq.push(mp(0, 1));
	visit[1] = true;

	while (!pq.empty())
	{
		pair<int, int> p = pq.top();
		pq.pop();
		for (int i = 0; i < node[p.second].size(); i++)
		{
			int to = node[p.second][i].first;
			int w = node[p.second][i].second;
			if (!visit[to] && -p.first + w < dist[to])
			{
				dist[to] = -p.first + w;
				pq.push(mp(-(-p.first + w), to));
			}
		}
	}
}

void dijkstra2()
{
	priority_queue<pair<int, int> > pq;
	FOR(i, N+1) dist[i] = INF;
	FOR(i, N+1) visit[i] = false;
	pq.push(mp(0, p1));
	visit[p1] = true;

	while (!pq.empty())
	{
		pair<int, int> p = pq.top();
		pq.pop();
		for (int i = 0; i < node[p.second].size(); i++)
		{
			int to = node[p.second][i].first;
			int w = node[p.second][i].second;
			if (!visit[to] && -p.first + w < dist[to])
			{
				dist[to] = -p.first + w;
				pq.push(mp(-(-p.first + w), to));
			}
		}
	}
}

void dijkstra3()
{
	priority_queue<pair<int, int> > pq;
	FOR(i, N + 1) dist[i] = INF;
	FOR(i, N + 1) visit[i] = false;
	pq.push(mp(0, p2));
	visit[p1] = true;

	while (!pq.empty())
	{
		pair<int, int> p = pq.top();
		pq.pop();
		for (int i = 0; i < node[p.second].size(); i++)
		{
			int to = node[p.second][i].first;
			int w = node[p.second][i].second;
			if (!visit[to] && -p.first + w < dist[to])
			{
				dist[to] = -p.first + w;
				pq.push(mp(-(-p.first + w), to));
			}
		}
	}
}
int main()
{
	freopen("input.txt", "r", stdin);
	int start_to_p1, start_to_p2, p1_to_p2, p1_to_N, p2_to_N;
	scanf("%d%d", &N, &E);
	FOR(i, E)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		node[u].push_back(mp(v, w));
		node[v].push_back(mp(u, w));
	}

	scanf("%d%d", &p1, &p2);
	dijkstra();
	start_to_p1 = dist[p1];
	start_to_p2 = dist[p2];
	if (start_to_p1 == INF || start_to_p2 == INF || dist[N] == INF)
	{
		printf("-1\n");
	}
	else
	{
		dijkstra2();
		p1_to_N = dist[N];
		p1_to_p2 = dist[p2];
		dijkstra3();
		p2_to_N = dist[N];

		printf("%d\n", MIN(start_to_p1 + p1_to_p2 + p2_to_N, start_to_p2 + p1_to_p2 + p1_to_N));
	}
	
	return 0;
}

jwg8679 6년 전 1

p1으로 가는 경로가 막혀있어도 p2로 갈 수 있으면 목적지까지 갈 수도 있습니다 -1 조건에서 or로 걸러버리시면 p1이 막혀있고 p2를 통해 목적지로 가는 경로를 못 찾을 것 같네요

DryType 6년 전 1

두개 다 들려야하니 한개 노드라도 막혀있으면 불가능한 경우 아닌가요?

DryType 6년 전 0

오타로 인한 오답이었습니다 ㅠㅠ

72 Line에 p2를 p1이라고 썻네요

#include <cstdio>
#include <vector>
#include <queue>
#define FOR(i,n) for(int i=0; i<n ; i++)
#define mp make_pair
#define MIN(a,b) ( (a)<(b)?(a):(b) )

using namespace std;

int dist[801];
int N, E, p1, p2;
bool visit[801];
const int INF = 987654321;
vector<pair<int, int> > node[801];

void dijkstra(int param)
{
	priority_queue<pair<int, int> > pq;
	FOR(i, N+1) dist[i] = INF;
	FOR(i, N+1) visit[i] = false;
	pq.push(mp(0, param));
	visit[param] = true;
	dist[param] = 0;
	while (!pq.empty())
	{
		pair<int, int> p = pq.top();
		pq.pop();
		for (int i = 0; i < node[p.second].size(); i++)
		{
			int to = node[p.second][i].first;
			int w = node[p.second][i].second;
			if (!visit[to] && -p.first + w < dist[to])
			{
				dist[to] = -p.first + w;
				pq.push(mp(-(-p.first + w), to));
			}
		}
	}
}
int main()
{
	freopen("input.txt", "r", stdin);
	int start_to_p1, start_to_p2, p1_to_p2, p1_to_N, p2_to_N;
	scanf("%d%d", &N, &E);
	FOR(i, E)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		node[u].push_back(mp(v, w));
		node[v].push_back(mp(u, w));
	}

	scanf("%d%d", &p1, &p2);
	dijkstra(1);
	start_to_p1 = dist[p1];
	start_to_p2 = dist[p2];
	if (start_to_p1 == INF || start_to_p2 == INF || dist[N] == INF)
	{
		printf("-1\n");
	}
	else
	{
		dijkstra(p1);
		p1_to_N = dist[N];
		p1_to_p2 = dist[p2];
		dijkstra(p2);
		p2_to_N = dist[N];

		printf("%d\n", MIN(start_to_p1 + p1_to_p2 + p2_to_N, start_to_p2 + p1_to_p2 + p1_to_N));
	}
	return 0;
}

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

문제

문제

출처

ICPC

90%에서 틀립니다.

DryType 6년 전 0

jwg8679 6년 전 1

DryType 6년 전 1

DryType 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말