글 읽기 - 1504 코드 질문

jkho1229 5년 전 0

안녕하세요 예외처리에서 잘못된건지 아니면 다익스트라에서 문제가 있는지 디버깅을 해봐도 잘 모르겠어서

질문드립니다. 어느 부분이 틀린걸까요..?

#define _CRT_SECURE_NO_WARNINGS
#define INF 200000001
#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

typedef struct Node {
	int node;
	long weight;
};

struct cmp {
	bool operator()(Node a, Node b) {
		return a.weight > b.weight;
	}
};

int N, E,node1,node2;
vector<Node> Graph[801];
long Dis[801];

void Dijkstra(int start) {
	for (int i = 1; i <= N; i++) {
		Dis[i] = INF;
	}
	Dis[start] = 0;

	priority_queue<Node, vector<Node>, cmp> pq;
	pq.push({ start,0 }); // pq 저장 destination , weight
	while (!pq.empty()) {
		int node = pq.top().node;
		int dis = pq.top().weight;
		pq.pop();
		if (dis > Dis[node]) continue;
		for (int i = 0; i < Graph[node].size(); i++)
		{
			int newNode = Graph[node][i].node;
			int newDis = Graph[node][i].weight + dis;
			if (newDis < Dis[newNode]) {
				Dis[newNode] = newDis;
				pq.push({ newNode,newDis });
			}
		}
	}
}

int main()
{
	scanf("%d %d", &N, &E);
	int a, b, c;
	for (int i = 1; i <= E; i++) {
		scanf("%d %d %ld", &a, &b, &c);
		Graph[a].push_back({ b,c });
	}
	
	scanf("%d %d", &node1, &node2);
	long long ans1 = 0,ans2 = 0;
	long long StoN1, StoN2;
	bool flag1= true,flag2 = true;
	Dijkstra(1);
	StoN1 = Dis[node1]; // 1 , node1
	StoN2 = Dis[node2]; // 1 , node2
	if (StoN1 > INF)  flag1 = false;
	if (StoN2 > INF) flag2 = false;
	if (flag1 == false && flag2 == false) {
		printf("-1\n");
		return 0;
	}
	
	long long N1toN2, N2toN;
	long long N2toN1, N1toN;
	Dijkstra(node1);
	N1toN2= Dis[node2]; // node1 , node2
	Dijkstra(node2);
	N2toN1= Dis[node1]; // node2 , node1

	if (N1toN2 > INF) flag1 = false;
	if (N2toN1 > INF) flag2 = false;
	if (flag1 == false && flag2 == false) {
		printf("-1\n");
		return 0;
	}
	Dijkstra(node2);
	N2toN = Dis[N]; // node2, N
	Dijkstra(node1);
	N1toN = Dis[N]; // node1 , N
	if (N2toN > INF) flag1 = false;
	if (N1toN > INF) flag2 = false;

	if (flag1 && flag2) {
		printf("%lld", min(StoN1 + N1toN2 + N2toN, StoN2 + N2toN1 + N1toN));
	}
	else if (flag1) {
		printf("%lld", StoN1 + N1toN2 + N2toN);
	}
	else if (flag2) {
		printf("%lld", StoN2 + N2toN1 + N1toN);
	}
	else {
		printf("-1\n");
	}
	
	return 0;
}

hello70825 5년 전 1

양방향 길인데 코드에서는 단방향 길로 되어있네요.

이 부분만 고치면 통과합니다.

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

문제

문제

출처

ICPC

1504 코드 질문

jkho1229 5년 전 0

hello70825 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말