글 읽기 - 선언과 초기화 관련 질문 (다익스트라)

shinbian11 3년 전 0

37,38번째 줄처럼 테스트 케이스 한번마다 d,visited 함수를 새로 생성하면 올바른 답이 나오는데,

왜 선언해놓고(20,21번째 줄) 테스트 케이스 한번마다 초기화하는 식(39,40번째 줄)으로 하면 올바른 답이 나오지 않나요?

전자와 후자가 사실상 같은 거 아닌가요? 서로 다른 답이 나오는 이유가 궁금합니다.

#include <bits/stdc++.h>

// F_I 사용하면 cin 과 scanf 를 섞어서 쓰면 안된다!
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;

ll Min(ll a, ll b) { return (a < b) ? a : b; }
ll Max(ll a, ll b) { return (a < b) ? b : a; }
ll gcd(ll m, ll n) { if (n == 0) return m; return gcd(n, m % n); } //최대공약수
ll lcm(ll m, ll n) { return m * n / gcd(m, n); } //최소공배수

int INF = 987654321;
vector<pi> v[10004];

//int d[10004];
//bool visited[10004];

int main()
{
	F_I;
	
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n, m, start;
		cin >> n >> m >> start;
		
		memset(v, 0, sizeof(v));


		vector<int> d(n + 1, INF); //올바른 값
		vector<bool> visited(n + 1, false); //올바른 값
		//memset(d, INF, sizeof(d)); //틀린 값
		//memset(visited,false, sizeof(visited)); //틀린 값

		for (int i = 0; i < m; i++)
		{
			int a, b, cost;
			cin >> a >> b >> cost;
			v[b].push_back({ a,cost });	
		}

		priority_queue< pi, vector<pi>, greater<pi> > q;
		d[start] = 0;

		q.push({ 0,start });
		while (!q.empty())
		{
			auto t = q.top();
			q.pop();
			int x = t.second;
			if (visited[x])
				continue;
			visited[x] = true;

			for (auto k : v[x])
			{
				int y = k.first;
				int cost = k.second;
				if (d[y] > d[x] + cost)
				{
					d[y] = d[x] + cost;
					q.push({ d[y],y });
				}
			}
		}
	
		int cnt = 0;
		int mx = -1;

		for (int i = 1; i <= n; i++)
		{
			if (d[i] == INF) continue;
			cnt += 1;
			if (mx < d[i])
				mx = d[i];
		}

		cout << cnt << ' ' << mx << '\n';
	}
	return 0;
}

shinbian11 3년 전 0

해결했습니다. fill을 대신 사용하니까 되네요.

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

문제

문제

출처

ICPC

선언과 초기화 관련 질문 (다익스트라)

shinbian11 3년 전 0

shinbian11 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말