글 읽기 - 무엇이 문제일까요??

jgjg7882 3년 전 0

일단 공격할 수 있는 타워와 그렇지 않은 타워를 분리시켜놓은 뒤 폴로이드 와샬를 통해 경로를 구했습니다.

그 다음 공격못하는 타워 각각 공격할 수 있는 타워까지 경로 중에 가장 긴 경로를 선택한 다음 bfs를 돌려서 해결 할려 했는데 실패했네요 ㅠㅠ 뭐가 문제 일까요???

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 101
#define INF 987654321
#define fst first
#define sec second
using namespace std;
struct Tree { int value, next; };
struct cs { int here, target; };
typedef pair<int, int> pii;
typedef vector<int> vi;
inline double cal(pii &a, pii &b) { return sqrt(pow(abs(a.fst - b.fst), 2) + pow(a.sec - b.sec, 2)); }

int n;
double r, d;
pii pos[MAX];
Tree dist[MAX][MAX];
vi att_idx;
vi non_idx;

void floyd() {
	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for (int j = 1; j <= n; j++) {
				if (i == k || j == k || i == j)continue;
				if (dist[i][j].value > dist[i][k].value + dist[k][j].value) {
					dist[i][j].value = dist[i][k].value + dist[k][j].value;
					dist[i][j].next = dist[i][k].next;
				}
			}
}

void init() {
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			dist[i][j].value = INF;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			if (i == j)continue;
			if (r >= cal(pos[i], pos[j])) {
				dist[i][j] = { 1,j };
				if (j == 0)att_idx.push_back(i);
			}
			else
				if (j == 0)non_idx.push_back(i);
		}
	}
}

double solve() {
	floyd();
	vector<double> energy(n + 1, d);
	double ans = 0;
	queue<cs> q;
	for (int i : non_idx) {
		pii p;
		for (int j : att_idx) {
			if (dist[i][j].value<INF && p.fst < dist[i][j].value) {
				p.fst = dist[i][j].value;
				p.sec = j;
			}
		}
		q.push({ i,p.sec});
	}


	while (!q.empty()) {
		cs c = q.front(); q.pop();
		int next = dist[c.here][c.target].next;

		if (c.here == c.target) continue;

		energy[next] += energy[c.here] / 2.0;
		energy[c.here] = 0;
		q.push({ next,c.target});
				
	}

	for (int i : att_idx)ans += energy[i];
	
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> r >> d;
	for (int i = 0; i <= n; i++)cin >> pos[i].fst >> pos[i].sec;
	init();
	cout << fixed;
	cout.precision(2);
	cout << solve() << "\n";

}

jpyo0803 1년 전 0

bfs를 사용해 적이 각 포탑까지 최소 몇번만에 도달할 수 있는지를 통해 답을 쉽게 구할 수 있습니다!

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

문제

문제

출처

ICPC

무엇이 문제일까요??

jgjg7882 3년 전 0

jpyo0803 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말