[정올 1108] 페이지 전환

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=388&sca=99&sfl=wr_hit&stx=1108 

JUNGOL

#include <stdio.h>

/*	서로 다른 A->B로 가는 총 클릭 횟수: 구해야 함
	서로 다른 A->B의 가짓수: nP2*/
int N, path[505][505], exist[505], checked[505], NodeCnt; //(i,j): i->j로 가는 방향
struct Node {
	int s, cnt; 
} buf[250000];
int s, e;
void push_back(int src, int count) {
	buf[e].s = src;
	buf[e++].cnt = count;
}
Node& pop() {
	return buf[s++];
}

int GetMinDist(int src, int dst) {//src->dst로 가는 최소 클릭수
	s = e = 0; //BFS 사용
	for (int i = 0; i < 501; i++) checked[i] = 0;
	push_back(src, 0);
	while (s <= e) {
		Node& rN = pop();
		checked[rN.s] = 1;
		int* mypath = path[rN.s];
		if (mypath[dst]) return rN.cnt + 1;
		for (int i = 1; i <= 500; i++) { //내꺼에 없으니, 한번씩 더 이동
			if (mypath[i] && checked[i] == 0) {
				push_back(i, rN.cnt + 1);
			}
		}
	}
	return -1;
}

int main(void) {
	int a, b, PageCb, Clicks = 0;
	scanf("%d", &N);
	//node가 총 몇 개인지는 안 나옴
	for (int i = 0; i < N; i++) {
		scanf("%d%d", &a, &b);
		path[a][b] = 1;
		if (exist[a] == 0) {
			exist[a] = 1; NodeCnt++;
		}
		if (exist[b] == 0) {
			exist[b] = 1; NodeCnt++;
		}
	}
	PageCb = NodeCnt * (NodeCnt - 1);
	for (int i = 1; i <= 500; i++) { //출발지 i
		if (exist[i] == 0) continue;
		for (int j = 1; j <= 500; j++) { //도착지 j
			if (exist[j] == 0 || i == j) continue;
			//i, j 정해짐
			int ans = GetMinDist(i, j);
			Clicks += ans;
		}
	}
	printf("%.3f\n", (double)Clicks/ (double)PageCb);

	return 0;
}