algorithm the tourist guide - andstudy/forge GitHub Wiki

  /* @JUDGE_ID:parkpd 110401 Cpp "test" */
  
  /* @BEGIN_OF_SOURCE_CODE */
  
  #include <iostream>
  #include <vector>
  #include <set>
  #include <string>
  #include <strstream>
  #include <algorithm>
  #include <map>
  #include <math.h>
  
  //#define _UNIT_TEST
  
  using namespace std;
  
  namespace ATUtil
  {
  
  bool IsInRange(int value, int from, int to)
  {
  	return (from <= value) && (value <= to);
  }
  
  int ConvertToIndex(char c)
  {
  	if ('a' <= c && c <= 'z')
  	{
  		return c - 'a';
  	}
  	else
  	{
  		return -1;
  	}
  }
  
  char ConvertToChar(int i)
  {
  	return (char)i + 'a';
  }
  
  typedef map<int, int> IntDB;
  typedef vector<int> Ints;
  
  };
  
  using namespace ATUtil;
  
  #ifdef _UNIT_TEST
  
  #include "../UnitTest++/src/UnitTest++.h"
  
  int main()
  {
  	UnitTest::RunAllTests();
  
  	char temp;
  	cin >> temp;
  
  	return 0;
  }
  
  #endif
  
  // code implement
  
  namespace ATCode
  {
  
  ///////////////////////////////////////////////////////////////
  // CTourGuide
  class CTourGuide
  {
  public:
  	CTourGuide() : m_Start(-1), m_Destiny(-1), m_Max(0), m_CityNum(0) {}
  
  	void Init(int cities, int roads);
  	void Connect(int from, int to, int capacity);
  	int NeedTrip(int start, int destiny, int tourists);
  	void _FindMaxTrip(int start);
  
  	struct Road
  	{
  		Road(int to, int capacity) : m_To(to), m_Capacity(capacity) {}
  		int m_To;
  		int m_Capacity;
  	};
  
  	struct City
  	{
  		City(int index) : m_Index(index), m_Checked(false), m_MaxCapacity(-1) {}
  
  		int m_Index;
  		bool m_Checked;
  		int m_MaxCapacity;
  		vector<Road> m_Neighbor;
  	};
  
  	int m_Start;
  	int m_Destiny;
  
  	int m_Max;
  
  	int m_CityNum;
  	vector<City> m_Cities;
  };
  
  void CTourGuide::Init(int cities, int roads)
  {
  	m_Cities.reserve(cities + 1);
  	m_Cities.push_back(City(-1));	// dummy
  	for (int i = 1; i <= cities; ++i)
  	{
  		m_Cities.push_back(City(i));
  	}
  
  	m_CityNum = cities;
  }
  
  void CTourGuide::Connect(int from, int to, int capacity)
  {
  	// bi-direction
  	m_Cities[from].m_Neighbor.push_back(Road(to, capacity));
  	m_Cities[to].m_Neighbor.push_back(Road(from, capacity));
  }
  
  int CTourGuide::NeedTrip(int start, int destiny, int tourists)
  {
  	m_Start = start;
  	m_Destiny = destiny;
  
  	City& s = m_Cities[m_Start];
  	s.m_MaxCapacity = 0x7fffffff;
  	
  	_FindMaxTrip(m_Start);
  
  	double maxTripCapacity = (double)(m_Cities[m_Destiny].m_MaxCapacity - 1);
  	int trip = (int)ceil(tourists / maxTripCapacity);
  	return trip;
  }
  
  void CTourGuide::_FindMaxTrip(int start)
  {
  	City& s = m_Cities[start];
  	if (s.m_Checked)
  	{
  		return;
  	}
  
  	s.m_Checked = true;
  
  	vector<int> needCheckRoads;
  
  	for (size_t i = 0; i < s.m_Neighbor.size(); ++i)
  	{
  		Road& toRoad = s.m_Neighbor[i];
  		City& toCity = m_Cities[toRoad.m_To];
  
  		if (toCity.m_Checked)
  		{
  			continue;
  		}
  
  		const int possibleCapacity = min(s.m_MaxCapacity, toRoad.m_Capacity);
  
  		// 현재 도시의 수용량이 이전 도시까지의 수용량 + 도로가 넓다면 ok			
  		if (possibleCapacity <= toCity.m_MaxCapacity)
  		{
  			// do nothing
  		}
  		// 현재 도시의 수용량보다 이전 도시까지의 수용량 + 도로가 넓다면 이걸 선택
  		else
  		{
  			toCity.m_MaxCapacity = possibleCapacity;
  		}
  
  		if (toCity.m_Index == m_Destiny)
  		{
  			continue;
  		}
  
  		needCheckRoads.push_back(toRoad.m_To);
  	}
  
  	for (size_t i = 0; i < needCheckRoads.size(); ++i)
  	{
  		_FindMaxTrip(needCheckRoads[i]);
  	}
  }
  
  ///////////////////////////////////////////////////////////////
  // CConsole
  class CConsole
  {
  public:
  	static void ConsoleTest(istream& input, ostream& output);
  };
  
  void CConsole::ConsoleTest(istream& input, ostream& output)
  {
  	int scenarioIndex = 1;
  
  	while (1)
  	{
  		int cities = 0;
  		int roads = 0;
  	
  		input >> cities >> roads;
  
  		if ((0 == cities) && (0 == roads))
  		{
  			break;
  		}
  
  		CTourGuide tourGuide;
  		tourGuide.Init(cities, roads);
  
  		int from = 0;
  		int to = 0;
  		int capacity = 0;
  
  		for (int i = 0; i < roads; ++i)
  		{
  			input >> from >> to >> capacity;
  			tourGuide.Connect(from, to, capacity);
  		}
  
  		int start;
  		int destiny;
  		int tourists;
  		input >> start >> destiny >> tourists;
  
  		output << "Scenario #" << scenarioIndex << "\n";
  		output << "Minimum Number of Trips = " << tourGuide.NeedTrip(start, destiny, tourists) << "\n";
  	}
  };
  
  }
  
  using namespace ATCode;
  
  #ifndef _UNIT_TEST
  
  int main()
  {
  	CConsole::ConsoleTest(cin, cout);
  
  	return 0;
  }
  
  #else
  
  // tests
  
  struct FixtureConsole
  {
  	stringstream input;
  	stringstream output;
  };
  
  TEST_FIXTURE(FixtureConsole, ConsoleTest1)
  {
  	input << 
  		"7 10\n"
  		"1 2 30\n"
  		"1 3 15\n"
  		"1 4 10\n"
  		"2 4 25\n"
  		"2 5 60\n"
  		"3 4 40\n"
  		"3 6 20\n"
  		"4 7 35\n"
  		"5 7 20\n"
  		"6 7 30\n"
  		"1 7 99\n"
  		"0 0\n"
  	;
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL("Scenario #1\nMinimum Number of Trips = 5\n", output.str());
  }
  
  TEST_FIXTURE(FixtureConsole, ConsoleTest2)
  {
  	input << 
  		"7 12\n"
  		"1 2 30\n"
  		"1 3 25\n"
  		"1 4 40\n"
  		"2 3 80\n"
  		"2 7 25\n"
  		"7 6 20\n"
  		"3 4 70\n"
  		"5 3 45\n"
  		"6 5 30\n"
  		"7 5 60\n"
  		"3 7 15\n"
  		"4 6 25\n"
  		"1 6 100\n"
  		"0 0\n"
  	;
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL("Scenario #1\nMinimum Number of Trips = 4\n", output.str());
  }
  
  
  #endif
  
  /* @END_OF_SOURCE_CODE */

  import java.util.ArrayList;
  
  
  public class Graph {
  	private int pointCount;
  	private int[][] nodes;
  	
  	public Graph(int pointCount) {
  		this.pointCount = pointCount;
  		nodes = new int[pointCount][pointCount];
  		for(int i=0;i<pointCount;i++){
  			for(int j=0;j<pointCount;j++){
  				nodes[i][j] = 0;
  			}
  		}
  	}
  	
  	
  	public void insertNode(int fromPoint, int toPoint, int weight) {
  		nodes[fromPoint][toPoint] = weight;
  		nodes[toPoint][fromPoint] = weight;
  		
  	}
  	public Path findMinPath(int fromPoint,int toPoint){
  		Path newPath= new Path(fromPoint);
  		return findMinPath( fromPoint, toPoint, newPath);
  	}
  	public Path findMinPath(int fromPoint,int toPoint,Path path){
  		if(fromPoint == toPoint){
  			return path;
  		}
  		ArrayList<Path> resultPaths = new ArrayList<Path>();
  		for(int i=0;i<pointCount;i++){
  			//검사할 노드가 연결되어 있고  이전에 방문하지 않았던 노드이면 다음 노드로 부터 탐색
  			if( nodes[fromPoint][i] > 0 ){
  				if(path.isVisitedNode(i)){
  					continue;
  				}
  				Path newPath = new Path(path);
  				newPath.addVisitedPoint(i, nodes[fromPoint][i]);
  				
  				Path searchedPath = findMinPath(i, toPoint,newPath);
  				if(searchedPath != null){
  					resultPaths.add(searchedPath);
  				}
  			
  			}
  		}
  		
  		Path minPath = null;
  		int minWeight = Integer.MAX_VALUE;
  		//가장 짧은 Path 찾아서 return
  		for(int i=0;i<resultPaths.size();i++){
  			Path curPath = resultPaths.get(i);
  			if(curPath.getPathWeight() < minWeight){
  				minPath = curPath;
  				minWeight = curPath.getPathWeight();
  			}
  		}
  		return minPath;
  	}
  
  }

  import java.util.ArrayList;
  
  
  public class Path {
  	private ArrayList<Integer> visitedPoint = new ArrayList<Integer>();
  	private int pathWeight =Integer.MAX_VALUE;
  	
  	public Path(Path fromPath){
  		visitedPoint.addAll(fromPath.visitedPoint);
  		pathWeight = fromPath.pathWeight;
  	}
  	
  	public Path(int fromPoint){
  		visitedPoint.add(fromPoint);
  	}
  	
  	public void addVisitedPoint(int point,int weight){
  		visitedPoint.add(point);
  		pathWeight = Math.min(pathWeight, weight);
  	}
  	public int getPathWeight() {
  		return pathWeight;
  	}
  	public void setPathWeight(int pathWeight) {
  		this.pathWeight = pathWeight;
  	}
  	
  	public boolean isVisitedNode(int point){
  		return visitedPoint.contains(point);
  	}
  	
  	public String toString(){
  		return "Paths : "+visitedPoint.toString()+"\nWeight:"+pathWeight;
  	}
  }

  import junit.framework.TestCase;
  
  
  public class GraphTestCase extends TestCase {
  	public void testInitGraph(){
  		Graph graph = new Graph(3);
  		graph.insertNode(0,1,10);
  		graph.insertNode(1,2,20);
  		graph.insertNode(2,0,30);
  		
  		Path minPath = graph.findMinPath(0, 2);
  		System.out.println(minPath);
  	}
  }