자료구조:: 최단거리 알고리즘 - City path

// 커피를 쏟아서 이전 자료구조 파일을 다 잃어버렸다 ㅠㅠ

// 잡담으로 파일이랑 채점 시스템의 입력 방식이 달라서 시간을 많이 썼다..

 

Floyd Warshall Algorithm의 응용

<소스 코드>

#include <iostream>
#include <vector>
using namespace std;

struct Node{
	int data;
	vector<int> neighbors;
};

class Graph{
	int num;
	Node* vertices;
	
public:
	Graph(int n) {
		num = n;
		vertices = new Node[n + 1];
	}
	
	int insertV(int data){
		vertices[data].data = data;
	}
	int insertE(int from, int to){
		vertices[from].neighbors.push_back(to);
	}
	
	bool IsNeighbor(int from, int to){
		for(int e : vertices[from].neighbors)
			if(e == to) return true;
		
		return false;
	}
	
	int findShortestPathMax(){
		int weights[num + 1];
		for(int i = 1; i < num + 1; i++)
			weights[i] = vertices[i].neighbors.size() - 1;

		int dist[num + 1][num + 1];
		for( int i = 1 ; i <= num; i++ ){
			for( int j = 1; j <= num; j++){
				if ( i == j ) dist[i][j] = 0;
				else if ( IsNeighbor(i, j) != false ) dist[i][j] = 1; 
				else dist[i][j] = 100;
			}
		}
		
		for( int k = 1; k <= num; k++){
			for( int i = 1 ; i <= num; i++ ){
				for( int j = 1; j <= num; j++) {
					if(dist[i][j] == 1) continue;
					if(dist[i][k] + dist[k][j] + weights[k] < dist[i][j]){
						dist[i][j] = dist[i][k] + dist[k][j] + weights[k];
					}
				}
						
			}
		}

		int max = 0;
		for( int i = 1 ; i <= num; i++ ){
			for( int j = 1; j <= num; j++){
				if(max < dist[i][j])
					max = dist[i][j];
			}
		}
		cout << max << endl;
	}
	
};
int main(){
	int n;
	cin >> n;
	
	Graph graph(n);

	int v, neighbor;
	for(int i = 1; i <= n; i++){
		cin >> v;
		graph.insertV(v);
		while(true){
			cin >> neighbor;
			if(neighbor == 0) {
				break;
			}
			graph.insertE(v, neighbor);
		}
	}

	graph.findShortestPathMax();
}