백준 10282 - 해킹(C++)

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

10282번: 해킹

다익스트라를 사용하는 문제입니다.

다익스트라 알고리즘을 통해 C번에서 탐색을 시작하면 되는 문제입니다.

void Dijstra(int x){
	Distance[x] = 0;
	q.push({0,x});
	while(!q.empty()){
		int X = q.top().second;
		long long cost = q.top().first;
		q.pop();
		for(int i = 0; i < line[X].size(); i++){
			int xx = line[X][i].first;
			long long Cost = line[X][i].second;
			if(Distance[xx] > Distance[X] + Cost){
				Distance[xx] = Distance[X] + Cost;
				q.push({Distance[xx], xx});
			}
		}
	}
}

우선 순위 큐에 (비용, 위치)를 넣어서 비용을 기준으로 오름차순으로 만들어줍니다.

queue에 top의 값을 통해 자신과 연결된 컴퓨터를 찾고, Distance 값을 조건에 따라 갱신해 줍니다.

 

 

이번에는 감염된 컴퓨터의 수와 최소 비용을 구하는 방법입니다.

void find_computer(){
	long long maxi = 0;
	int cnt = 0;
	for(int i = 1; i <= N; i++){
		if(Distance[i] != INF){
			cnt++;
			maxi = max(maxi, Distance[i]);
		}
	}
	cout << cnt << " " << maxi << "\n";
}

먼저 Distance의 값이 INF가 아니라면, 감염된 컴퓨터라는 의미입니다.

따라서 cnt를 증가해줬습니다.

또한, Distance의 값이 INF가 아닌 것 중에서, 최댓값을 가지고 있다면, 가장 마지막으로 방문된 지점이라는 의미입니다.

따라서 가장 큰 값으로 maxi 값을 저장해줍니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>
#define INF 98765432100

using namespace std;

int N, M, start;
long long Distance[10001];
priority_queue<pair<long long,int>, vector<pair<long long,int>> , greater<pair<long long,int>>> q;
vector<pair<int,int>> line[10001];

void reset_distance(){
	for(int i = 1; i <= N; i++){
		Distance[i] = INF;
	}
}

void Dijstra(int x){
	Distance[x] = 0;
	q.push({0,x});
	while(!q.empty()){
		int X = q.top().second;
		long long cost = q.top().first;
		q.pop();
		for(int i = 0; i < line[X].size(); i++){
			int xx = line[X][i].first;
			long long Cost = line[X][i].second;
			if(Distance[xx] > Distance[X] + Cost){
				Distance[xx] = Distance[X] + Cost;
				q.push({Distance[xx], xx});
			}
		}
	}
}

void find_computer(){
	long long maxi = 0;
	int cnt = 0;
	for(int i = 1; i <= N; i++){
		if(Distance[i] != INF){
			cnt++;
			maxi = max(maxi, Distance[i]);
		}
	}
	cout << cnt << " " << maxi << "\n";
}

void solve(int cnt){
	reset_distance();
	Dijstra(start);
	find_computer();
	for(int i = 0; i <= N; i++) line[i].clear();
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	int test_case;
	cin >> test_case;
	for(int i = 1; i <= test_case; i++){
		cin >> N >> M >> start;
		for(int j = 1; j <= M; j++){
			int x, y, cost;
			cin >> x >> y >> cost;
			line[y].push_back({x,cost});
		}
		solve(start);
	}
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요