[백준 10282] 해킹 (C++)

문제 링크: https://www.acmicpc.net/problem/10282

10282번: 해킹

1. 주의할 점

- 단방향 그래프다

- 다익스트라 알고리즘을 사용하면 되며, 매 TC마다 V[] 벡터와,Dist[] 배열을 초기화 해줘야 한다

 

2. 구현

- 입력받는 그래프의 정보를 V[]에 모두 저장한다

- 시작점을 기준으로 우선순위큐를 사용하여 다익스트라 알고리즘을 통해 각 Node까지의 최단거리를 구한다

- 1~Node의 수 만큼 확인하면서 Dist[]값이 Max가 아니면 Cnt++하고 Result와 비교하여 더 크다면 갱신한다

 

#define MAX 987654321
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
struct info {
	int idx, val;
};
info tmp;
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
vector<info> v[10001];
int dist[10001], node, edge, start, s, e, val, test, cnt, result;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> test;
	for (int t = 0; t < test; t++) {
		cin >> node >> edge >> start;
		for (int i = 1; i <= node; i++) {
			v[i].clear();
			dist[i] = MAX;
		}
		for (int i = 0; i < edge; i++) {
			cin >> e >> s >> val;
			tmp.idx = e;
			tmp.val = val;
			v[s].push_back(tmp);
		}
		dist[start] = 0;
		result = -1;
		cnt = 0;
		priority_queue<info, vector<info>, cmp> pq;
		tmp.idx = start;
		tmp.val = 0;
		pq.push(tmp);
		while (!pq.empty()) {
			int cidx = pq.top().idx;
			int cv = pq.top().val;
			pq.pop();
			if (dist[cidx] < cv) continue;
			for (int i = 0; i < v[cidx].size(); i++) {
				int next = v[cidx][i].idx;
				int nv = v[cidx][i].val;
				if (dist[next] > cv + nv) {
					dist[next] = cv + nv;
					tmp.idx = next;
					tmp.val = cv + nv;
					pq.push(tmp);
				}
			}
		}
		for (int i = 1; i <= node; i++) {
			if (dist[i] != MAX) {
				cnt++;
				result = max(result, dist[i]);
			}
		}
		cout << cnt << " " << result << '\n';
	}
	system("pause");
	return 0;
}