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

zas777 3년 전 0

혹시 잘못 된 점이 있으면 찾아주세요 ㅠ

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define MAX 802
#define INF 1e9

int n, e, a, b, ans;
int dist[MAX];
vector<pair<int, int> > v[MAX];
void dijkstra(int start) {
	priority_queue<pair<int, int> > pq;
	dist[start] = 0;
	pq.push(make_pair(0, start));
	while (!pq.empty()) {
		int cost = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i].first;
			int nextCost = v[cur][i].second;
			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push(make_pair(-dist[next], next));
			}
		}
	}
}
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> e;
	for (int i = 0; i < e; i++) {
		int x, y, c;
		cin >> x >> y >> c;
		v[x].push_back(make_pair(y, c));
		v[y].push_back(make_pair(x, c));
	}
	cin >> a >> b;
	bool flagA = true;
	bool flagB = true;
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dijkstra(1);
	int route1 = dist[a];
	int route2 = dist[b];
	if (route1 == INF)
		flagA = false;
	if (route2 == INF)
		flagB = false;
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dijkstra(a);
	if (flagA == true) {
		route1 += dist[b];
	}
	if (flagB == true) {
		route2 += dist[b];
	}
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dijkstra(b);
	if (flagA == true)
		route1 += dist[n];
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dijkstra(a);
	if (flagB == true)
		route2 += dist[n];
	if (flagA == false && flagB == false) {
		ans = -1;
	}
	else {
		if (route1 < route2)
			ans = route1;
		else if (route2 < route1) {
			ans = route2;
		}
	}
	if (ans == INF)
		ans = - 1;
	cout << ans << '\n';
	return 0;
}

kuuku123 2년 전 1

저도 100 프로에서 틀렸습니다 떠서 하나고쳤는데 그 경우가 노드가 2개이고 연결되어있지 않은 경우 였습니다

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

문제

문제

출처

ICPC

100%에서 틀립니다

zas777 3년 전 0

kuuku123 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말