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

illiboy1212 4년 전 0

어디가 잘못된거 일까용.... 데이터 집어넣으면서 확인도 해주었습니당

#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 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++)
		{

			if(mapping[v[k][i].first] > v[k][i].second + cost)
			{
				mapping[v[k][i].first] = v[k][i].second + cost;
			}
			pq.push(make_pair(-mapping[v[k][i].first], v[k][i].first) );
		}
	}
	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);

	long long sum = ans > pns ? pns : ans;

	if (sum >= INF  || sum < 0)
	{
		printf("-1");
	}
	else printf("%lld\n", sum );
}

loveto3 4년 전 3

반례찾았슴다~

3 3

1 3 20

1 2 15

2 3 6

1 3

출력 : 20 나와야하는데

60나오시네엽

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

문제

문제

출처

ICPC

90%에서 틀립니다

illiboy1212 4년 전 0

loveto3 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말