[C++]백준 - 11780번 문제

11780번: 플로이드 2 (acmicpc.net)

11780번: 플로이드 2

 

11780번 : 플로이드 2

---

n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

 

 

출력

---

먼저, n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

그 다음에는 n×n개의 줄을 출력해야 한다. i×n+j번째 줄에는 도시 i에서 도시 j로 가는 최소 비용에 포함되어 있는 도시의 개수 k를 출력한다. 그 다음, 도시 i에서 도시 j로 가는 경로를 공백으로 구분해 출력한다. 이때, 도시 i와 도시 j도 출력해야 한다. 만약, i에서 j로 갈 수 없는 경우에는 0을 출력한다.

 

---

 

생각해 볼 점

---

플로이드 와샬 - YouTube

 

플로이드 와샬 알고리즘을 이해하게 되면, PI 배열을 만들어 역추적까지 실행할 수 있습니다.

 

 

 

코드

---

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define INF 100000000

int main() 
{
	int N, M;
	scanf("%d\n%d", &N, &M);
	
	//동적 할당
	int **map = new int*[N];
	int **pi = new int*[N];
	for(int i = 0; i < N; i++)
	{
	    map[i] = new int[N];
	    pi[i] = new int[N];
	    fill_n(map[i], N, INF);
	    fill_n(pi[i], N, -1);
	    
	    map[i][i] = 0;
	}
	
	//입력부
	for(int i = 0; i < M; i++)
	{
	    int a, b, c;
	    scanf("%d %d %d", &a, &b, &c);
	    a--; b--;
	    if(c < map[a][b]) 
	    {
	        pi[a][b] = a;
	        map[a][b] = c;
	    }
	}
	
	//플로이드 와샬
	for(int k = 0; k < N; k++)
	{
	    for(int j = 0; j < N; j++)
	    {
	        for(int i = 0; i < N; i++)
	        {
	            if(map[i][k] + map[k][j] < map[i][j])
	            {
	                map[i][j] = map[i][k] + map[k][j];
	                pi[i][j] = k;
	            }
	        }
	    }
	}
	
	//출력부
	for(int i = 0; i < N; i++) 
	{
	    for(int j = 0; j < N; j++) printf("%d ", map[i][j] == INF ? 0 : map[i][j]);
	    printf("\n");
	}
	//Pi 배열을 통한 경로 역추적
	for(int i = 0; i < N; i++) 
	{
	    for(int j = 0; j < N; j++) 
	    {
	        if(pi[i][j] == -1) printf("0");
	        else
	        {
	            vector<int> v;
	            stack<pair<int, int>> st;
	            st.push({i, j});
	            while(!st.empty())
	            {
	                int f = st.top().first;
	                int t = st.top().second;
	                
	                st.pop();
	                if(pi[f][t] == -1) v.push_back(f + 1);
	                else
	                {
	                    int k = pi[f][t];
	                    if(k != f) st.push({k, t});
	                    if(k != t) st.push({f, k});
	                }
	            }
	            v.push_back(j + 1);
	            printf("%d ", v.size());
	            for(int path : v) printf("%d ", path);
	        }
	        printf("\n");
	    }
	}
	
	//동적할당 해제
	for(int i = 0; i < N; i++) 
	{
	    delete[] map[i];
	    delete[] pi[i];
	}
	delete[] pi;
	delete[] map;
	return 0;
}

 

그 외

---