글 읽기 - 출력 시 경유하는 도시의 순서도 맞아야할까요?

051ssaa 2년 전 0

제목과 같습니다..!

틀렸다고 나오는데 다른 점이 도시가 출력되는 순서가 전부라서요ㅠㅠ

경유하는 도시의 순서가 정답에 영향을 미칠까요??

#include <iostream>
#include <vector>
#include <set>
#define INF 999999999
using namespace std;


int main(){
    int n, m; cin >> n >> m;
    int min_cost[101][101];
    set<int> through[101][101]; // i에서 j로 가기 위해 경유하는 도시
    
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j) min_cost[i][j] = 0;
            else min_cost[i][j] = INF;
        }
    }
    for(int i=0; i<m; i++){
        int a, b, c; cin >> a >> b >> c;
        min_cost[a][b] = min(min_cost[a][b], c);
    }
    
    /* floyd warshall */
    for(int mid=1; mid<=n; mid++){
        for(int src=1; src<=n; src++){
            for(int dst=1; dst<=n; dst++){
                if(min_cost[src][mid]+min_cost[mid][dst] < min_cost[src][dst]){
                    min_cost[src][dst] = min_cost[src][mid]+min_cost[mid][dst];
                    
                    through[src][dst].clear();
                    for(int city : through[src][mid]){
                        through[src][dst].insert(city);
                    }
                    through[src][dst].insert(mid);
                    for(int city : through[mid][dst]){
                        through[src][dst].insert(city);
                    }
                }
            }
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(min_cost[i][j] == INF) cout << "0" << " ";
            else cout << min_cost[i][j] << " ";
        }
        cout << endl;
    }
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == j || min_cost[i][j] == INF){
                cout << "0" << endl;
                continue;
            }
            cout << through[i][j].size()+2 << " ";
            cout << i << " ";
            for(int city : through[i][j]){
                cout << city << " ";
            }
            cout << j;
            cout << endl;
        }
    }
    
    return 0;
}

051ssaa 2년 전 0

순서도 맞아야 하는 거였네요...ㅎㅎㅎㅎ

경로를 set말고 vector로 저장하니 성공했습니다!

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

문제

문제

출처

ICPC

출력 시 경유하는 도시의 순서도 맞아야할까요?

051ssaa 2년 전 0

051ssaa 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말