글 읽기 - 80퍼에서 틀리는데 머가문제죠 ㅠ

wlshddlek 3년 전 0

설명은 주석에 달아놨습니다. 80퍼에서 틀리네요 ㅠ

해결 ) 아 생각없이 INF를 너무 작게잡았었네요 ㅠ

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n, m;
int result[20005];
vector<pair<int, int>> a[20005];
void dik(int start)
{
	for (int i = 1; i <= n; i++)      //result 배열을 최대값으로 채워줌
	{
		result[i] = 1000;
	}
	priority_queue<pair<int, int>> q;    //최소 노드부터 확인하기위해 우선순위큐사용
	q.push(make_pair(0, start));       //시작 노드 삽입
	result[start] = 0;
	while (!q.empty())
	{
		int node = q.top().second;          //현재노드 
		int distance = -q.top().first;       //거리 (우선순위큐는 값이큰순으로 정렬되기에 -를 붙임
		q.pop();
		if (distance > result[node])continue;                    //distance가 result보다 작으면 걸러내기 ,->굳이 할필요는없지만 조금이라도 빠르게하기위해
		for (int i = 0; i < a[node].size(); i++)        
		{
			int nextnode = a[node][i].first;              //현재노드로부터 연결된 다음노드
			int nextdistance = a[node][i].second;
			if (result[nextnode] > result[node] + nextdistance)           //새로운값이 더 작으면 result에 새로운최소거리 저장
			{
				result[nextnode] = result[node] + nextdistance;
				q.push(make_pair(-result[nextnode], nextnode));    //값이큰순으로 정렬되니 -를 붙여서 삽입
			}
		}
	}
}
int main()
{
	int start;
	cin >> n >> m >> start;
	for (int i = 0; i < m; i++)
	{
		int n1, n2, dis;
		cin >> n1 >> n2 >> dis;
		a[n1].push_back(make_pair(n2, dis));
	}
	dik(start);
	for (int i = 1; i <= n; i++)
	{
		if (result[i] == 1000)printf("INF\n");
		else
		printf("%d\n", result[i]);
	}
	return 0;
}

djm03178 3년 전 1

https://www.acmicpc.net/board/...

wlshddlek 3년 전 0

INF를 너무 작게했었네요 ㅠ 이런 사소한것들을 안놓치는 연습을 해야겠네요 ㅠ

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

문제

문제

출처

ICPC

80퍼에서 틀리는데 머가문제죠 ㅠ

wlshddlek 3년 전 0

djm03178 3년 전 1

wlshddlek 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말