글 읽기 - 틀린 케이스가 뭔지 모르겠습니다.

tddhot2 7년 전 0

일단 시간안에와 가지고 있는 금액 안에라는 말이 애매모호하여

여러가지 조건으로 해봤습니다.

예를 들어, 3시간안에 4000원으로 가야한다 이면

1) 도착했을 때 시간 <=180 , 도착했을 때 합계금액 <=4000

2) 도착했을 때 시간 < 180 , 도착했을 때 합계금액 <=4000

일단 금액은 4000원을 가지고 있고, 다 써도 가기만하면 되니깐 같아도 되는 것 같지만

도착했을 때 는 정각에맞추면 수업이 늦은거라고 생각할 수 있기 때문에 둘 다 해봤는데

정답이안되네요.. 일단 문제에 주어진 테스트케이스는 맞췄습니다.

그리고 알고리즘을 설명하자면

- 모든 경로를 방문하면서 시간 혹은 금액이 넘었을 경우 그 경로는 더 이상 탐방안한다.

- 시간 금액이 안 넘는 경우 방문한 정점에서 다시 탐색을 해 방문 안한 지점으로 간다.

이겁니다..

고수님들 도와주세요 ㅠㅠ 중간고사도 개망해서 기분이 참 착잡합니다..

#include <iostream>
using namespace std;
typedef struct _weight {
	int time;
	int money;
}Weight;


//The Array checking which node was visited
int Visited[101] = { 0, };
int MinMoney = 99999;

void DFS(Weight (*graph)[101], int nownode, int goalnode, int n, int nowtime, int nowmoney, int limittime,int limitmoney)
{
	Visited[nownode] = 1;

	if (nownode == goalnode)
	{
		if (nowmoney < MinMoney)
			MinMoney = nowmoney;
	}
	else
	{
		for (int i = 1; i <= n; i++)
		{
			//The conditions are i-node is abjacent with nownode, isn't visited, that Total time is not overing from limittime
			if (graph[nownode][i].time > 0 && Visited[i] == 0&& (nowtime + graph[nownode][i].time)<limittime
				&& (nowmoney + graph[nownode][i].money) <= limitmoney)
			{
				DFS(graph, i,goalnode,n, nowtime + graph[nownode][i].time, nowmoney + graph[nownode][i].money, limittime, limitmoney);
			}
		}
	}

	Visited[nownode] = 0;
}

int main()
{
	int N; //The num of building
	Weight AbjacentArray[101][101] = { 0 }; //Abjacent Array
	cin >> N;


	//State(Time,Money) of Junha
	int HaveTime, HaveMoney;
	cin >> HaveTime;
	cin >> HaveMoney;

	//The num of Edge
	int NumEdge;
	cin >> NumEdge;


	//Enter Weight of Edge to Abjacent Array
	for (int i = 0; i < NumEdge; i++)
	{
		int BuildingA, BuildingB, WeightTime, WeightMoney;
		cin >> BuildingA;
		cin >> BuildingB;
		cin >> WeightTime;
		cin >> WeightMoney;

		AbjacentArray[BuildingA][BuildingB].time = WeightTime;
		AbjacentArray[BuildingA][BuildingB].money = WeightMoney;
		AbjacentArray[BuildingB][BuildingA].time = WeightTime;
		AbjacentArray[BuildingB][BuildingA].money = WeightMoney;
	}


	DFS(AbjacentArray, 1, 5, N, 0, 0, HaveTime, HaveMoney);

	if (MinMoney == 99999)
		cout << -1 << endl;
	else
		cout << MinMoney << endl;
    return 0;
}

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