글 읽기 - 맞게 코딩 한거 같은데,,, 에러가 나네용

illiboy1212 4년 전 0

짤막하게 말씀드리자면 다익스트라를 두개의 경로로 쪼개서 (1 - a- b- n, 1 - b - a- n) 계산하는 방법을 이용해 각각 세번씩 돌렸는데 바로 틀렸습니다가 뜹니다...ㅠ 왜그런지 아시는 분 계신가용,,,?

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

const int INF = 1000000000;

vector< pair<int, int> > v[1010];

priority_queue< pair<int, int> > pq;

long long mapping[1010];

int visited[1010];

int n; // 정점의 개수
int k; // 간선의 개수

long long int dijk(int a, int b)
{
	for (int i = 1; i <= n ; i++)
	{
		mapping[i] = INF;
		visited[i] = 0;
	}

	pq.push(make_pair(0, a));
	visited[a] = -1;

	while(!pq.empty())
	{
		int k = pq.top().second; // 정점
		int cost = pq.top().first; // 비용

		pq.pop();

		if (visited[k]>=1)	continue;
		visited[k]++;

		for (int i = 0; i < v[k].size(); i++)
		{

			pq.push(make_pair(v[k][i].second, v[k][i].first) );

			if(mapping[v[k][i].first] > v[k][i].second + cost)
			{
				mapping[v[k][i].first] = v[k][i].second + cost;
			}
		}
	}
	return mapping[b];
}

int main()
{
	
	cin >> n;
	cin >> k;

	for (int i = 0; i < k; i++)
	{
		int a, b, c;
		 cin >> a >> b >> c;
		 v[a].push_back(make_pair(b ,c ));
		 v[b].push_back(make_pair(a ,c ));
	}

	int s, e;
	cin >> s >> e;

	long long pns = 0; // 1-> s -> e -> n;의 경우
	long long ans = 0; // 1-> e -> s -> n;의 경우

	pns += dijk(1, s);
	pns += dijk(s, e);
	pns += dijk(e, n);

	ans += dijk(1, e);
	ans += dijk(e, s);
	ans += dijk(s, n);

	printf("%lld\n", pns > ans ? ans : pns);
}

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

문제

문제

출처

ICPC

맞게 코딩 한거 같은데,,, 에러가 나네용

illiboy1212 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말