The Tourist Guide

문제 요약 : 출발 지점과 도착지점이 정해진 상태.

버스기사가 승객을 데리고 출발점에서 도착점까지 이동해야 합니다. 

하지만 승객 수가 많고, 각 도시간의 길에는 제한 인원이 있기 때문에 1번 이상의 trip이 필요합니다.

최소한의 trip수로 모든 승객을 다 도착지로 보내는 문제입니다.

문제 링크

해결 방법 : 다익스트라 알고리즘을 활용했습니다.

결과 : Accepted

소스 코드

#include<iostream>


using namespace std;

int N, R;
int c1, c2, p;
int start, dest, numOfTourists;
int line[101][101];
int value[101];
bool check[101];
int cur;

void init() {
	for(int i = 1; i <= 100; i++) {
		check[i] = false;
		value[i] = 0;
		for(int j = 1; j <= 100; j++) {
			line[i][j] = -1;
		}
	}
}

int calc() {
	check[start] = true;
	value[start] = 0;
	cur = start;
	
	while(true) {
		for(int i = 1; i <= 100; i++) {
			if(line[cur][i] != -1) {
				if(check[i]) continue;

				int temp;
				if(value[cur] > line[cur][i]) {
					temp = line[cur][i];
				} else {
					temp = value[cur];
				}

				if(value[i] == 0) {
					//i번째 vertex의 값이 비어 있다.
					value[i] = line[cur][i];
				} else if(value[i] < temp) {
					//i번째 vertext 값보다 현재 vertex 값에서 i번 vetex로 향하는 엣지의 합이 더 큰 경우
					value[i] = temp;
				} else if(value[i] > temp) {
					line[i][cur] = line[cur][i] = -1;
				}
			}
		}

		int max = -1;
		int index = 0;
		for(int i = 1; i <= 100; i++) {
			if(check[i] || value[i] == 0) continue;
			if(max < value[i]) {
				max = value[i];
				index = i;
			}
		}
		
		check[index] = true;
		cur = index;
		if(cur == dest) return value[dest];
	}
}

int calc2(int maxNum) {
	int num = 1;
	int addingNum = maxNum - 1;
	int sum = 0;
	while(true) {
		sum += addingNum;
		if(sum >= numOfTourists) return num;
		num++;
	}
}

int main() {
	//freopen("input.txt", "r", stdin);

	int index = 1;
	while(true) {
		cin >> N >> R;
		if(N == 0 && R == 0) break;

		init();

		for(int i = 0; i < R; i++) {
			cin >> c1 >> c2 >> p;
			line[c1][c2] = p;
			line[c2][c1] = p;
		}
		cin >> start >> dest >> numOfTourists;
		//end of input

		int result = calc();
		cout << "Scenario #" << index << endl;
		cout << "Minimum Number of Trips = " << calc2(result) << endl << endl;
		index++;
	}

	return 0;
}