글 읽기 - 다익스트라 한번만 봐주세요.

his130 6년 전 0

로직은 다익스트라로 매 정점을 돌린 후

p 배열에 이전의 노드를 넣어서, 그 값을 구하는 방식입니다.

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

const int INF = 987654321;
int main()
{
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin >> n >> m;

	vector<vector<pair<int, int>>> node(n + 1);

	while (m--)
	{
		int from, to, w;
		cin >> from >> to >> w;
		node[from].push_back({ to,w });
		node[to].push_back({ from,w });
	}

	for (int i = 1; i <= n; i++)
	{
		vector<int> dist(n + 1, INF);
		vector<int> p(n + 1);
		priority_queue<pair<int, int>> q;
		for (int j = 1; j <= n; j++)
		{
			p[j] = j;
		}
		dist[i] = 0;
		q.push({ dist[i],i });

		while (!q.empty())
		{
			int cost = -q.top().first;
			int here = q.top().second;
			q.pop();

			if (dist[here] < cost)
			{
				continue;
			}

			for (int d = 0; d < node[here].size(); d++)
			{
				int there = node[here][d].first;
				int w = node[here][d].second;

				if (dist[there] > cost + w)
				{
					p[there] = here;
					dist[there] =cost + w;
					q.push({ -dist[there],there });
				}
			}
		}

		for (int k = 1; k <= n; k++)
		{
			if (i == k)
			{
				cout << "- ";
			}
			else
			{
				int t = k;
				while (p[t] != i)
				{
					t = p[t];
				}

				cout << t <<" ";
			}
		}

		puts("");
	}

	return 0;
}

bupjae 6년 전 1

ios::sync_with_stdio(false) 의 의미는 C++ 입출력 루틴(예: cin, cout, ...)과 기존 C 입출력 루틴 (예: scanf, printf, gets, puts, ...)의 동기화를 하지 않겠다는 뜻입니다.

그럼에도 불구하고 이 프로그램은 출력에 cout 와 puts 를 같이 쓰고 있습니다. 이럴 경우 출력 순서는 뒤죽박죽이 될 수 있습니다.

his130 6년 전 0

감사합니다 며칠을 헤메다가 답을 구했어요 ㅠㅠ

his130 6년 전 0

그렇다면 혹시 \n 이런것도 못 쓰고 endl만 써야 하나요?

bupjae 6년 전 0

cout << "\n"; 은 사용할 수 있습니다.

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

문제

문제

출처

ICPC

다익스트라 한번만 봐주세요.

his130 6년 전 0

bupjae 6년 전 1

his130 6년 전 0

his130 6년 전 0

bupjae 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말