백준 11780 플로이드2 풀이(C++/CPP)

문제링크 : https://www.acmicpc.net/problem/11780

문제 접근

• 기본 플로이드 문제와 유사
• 단 경로를 구하는 문제가 다름
  • 현재 노드에서 다음 경로를 기록할 nxt 배열을 추가
  • nxt 배열을 갱신할때
    • 처음에 경로 map 배열에 초기화할떄
    • map[j][i] > map[j][k] + map[k][i] 인경우, nxt[j][i] = nxt[j][k]로 갱신
    • 이때 다음 노드는 k가 아닌, j에서 k로 가는 노드로 대체
      

시간복잡도 계산

• O(V^3) >> 1e6

인트 계산

• 버스 최대 비용 : 1e5
• 도시 최대 거치는 개수 : 1e2
• 최대 비용 : 1e5*1e2 = 1e7 >> INT 사용 가능

코드

#include <iostream>
#include <vector>
 
using namespace std;
 
const int inf = 1e8+10;
int map[110][110];
int nxt[110][110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&map[0][0], &map[109][110], inf);
    
    int V,E; cin >> V >> E;
    
    // 자기 자신으로 가는 비용은 0으로 초기화
    for(int i=1; i<=V; i++) map[i][i] = 0;
    
    for(int i=0; i<E; i++) {
        int a,b,c; cin >> a >> b >> c;
        map[a][b] = min(c, map[a][b]);
        nxt[a][b] = b;
    }
    
    
    for(int k=1; k<=V; k++) {
        for(int j=1; j<=V; j++) {
            for(int i=1; i<=V; i++) {
                // k를 거치는 경우 더 비용이 작으면 갱신
                // 이때 다음 노드는 k가 아닌, j에서 k로 가는 노드로 대체
                if(map[j][i] > map[j][k] + map[k][i]) {
                    map[j][i] = map[j][k] + map[k][i];
                    nxt[j][i] = nxt[j][k];
                }
            }
        }
    }
    
    for(int j=1; j<=V; j++) {
        for(int i=1; i<=V; i++) {
            if(map[j][i] == inf) cout << 0 << ' ';
            else cout << map[j][i] << ' ';
        }
        cout << '\n';
    }
    
    for(int j=1; j<=V; j++) {
        for(int i=1; i<=V; i++) {
            if(map[j][i] == inf || map[j][i] == 0) {
                cout << 0 << '\n';
                continue;
            }
            
            vector<int> v;
            // 출발지부터 nxt따라가면서 경로 추가
            int cur = j;
            
            while(cur != i) {
                v.push_back(cur);
                cur = nxt[cur][i];
            }
            v.push_back(cur);
            
            cout << v.size() << ' ';
            for(int x : v) cout << x << ' ';
            cout << '\n';
        }
    }
    
    
    return 0;
    
}
 
 
 

문제유형

• 플로이드 - 경로구하기