BOJ - 10282번 해킹 (C++)

문제 출처: https://www.acmicpc.net/problem/10282

문제 난이도

Gold 4

문제 접근법

다익스트라라고 듣고 보니깐 다익스트라로 풀 수 있는 방법이 보였지만, 그 전까지는 살짝 헤맸다.
일단 무방향이 아니라 b->a 방향인 점을 확인하자!
해킹당한 마지막 번호까지 간다면 이미 다 더해진 시간값이기 때문에 방문한 노드 중 제일 큰 시간값을 출력해주면 된다.

통과 소스

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define INF 987654321

using namespace std;


int dp[10001];

void dikstra(vector<vector<pair<int,int>>> arr, int start,int n) {
	dp[start] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
	pq.push({ 0,start });
	while (!pq.empty()) {
		int time = pq.top().first;
		int node = pq.top().second;
		pq.pop();
		for (auto x : arr[node]) {
			int next = x.first;
			int nextTime = x.second + time;
			if (dp[next] > nextTime) {
				dp[next] = nextTime;
				pq.push({ nextTime, next });
			}
		}
	}
	int comCnt = 0;
	int comTime = 0;
	for (int i = 1; i <= n; i++) {
		if (dp[i] != INF) {
			comCnt++;
			if (dp[i] > comTime) comTime = dp[i];
		}
	}
	cout << comCnt << " " << comTime << "\n";
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n, d, c;
		cin >> n >> d >> c;
		vector<vector<pair<int, int>> > arr(n + 1);
		for (int i = 0; i < d; i++) {
			int a, b, s;
			cin >> a >> b >> s;
			arr[b].push_back({ a,s });
		}
		for (int i = 1; i <= n; i++) dp[i] = INF;
		dikstra(arr, c, n);
	}
	


	return 0;
}

피드백

처음에 걍 이중배열을 놓고 풀었는데, 메모리초과가 나서 파라미터로 넘기는 형식으로 재구성했다. -다른 분의 코드를 참고-