글 읽기 - 플루이드워셜2 왜틀렸는지 잘모르겠어요!

qkrwjdfbf 7년 전 0

재귀를 이용해서 경로의 마지막값부터 차례대로 스택에 넣은뒤 스택을 출력하는식으로 추적했어요

고수님들 틀린 부분좀 알려주세요 ㅠㅠ

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <cstring>
using namespace std;
int n,m;
stack<int> st;

int dv[110][110];
int via[110][110];
void func(int i,int j){
    int pre = j;
    pre = via[i][pre];
    if(pre==i)
        st.push(pre);
    else{
        func(pre,j);
        func(i,pre);
    }
}
int main(){
    scanf("%d",&n);
    scanf("%d",&m);
    int s,e,g;
   // memset(dv,0x3f,sizeof(dv));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)    dv[i][j] = 0;
           else    dv[i][j] = 987654321;
            via[i][j] = -1;
        }
    }
    

    for(int i=0;i<m;i++){
        scanf("%d %d %d",&s,&e,&g);
        if(dv[s][e]>g){
        dv[s][e] = g;
        via[s][e] = s;
        }
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)    continue;
            if(dv[j][i]>=987654321) continue;
            for(int k=1;k<=n;k++){
              if(i==k||j==k||dv[i][k]>=987654321)  continue;
                if(dv[j][k]>dv[j][i]+dv[i][k]){
                dv[j][k] = dv[j][i]+dv[i][k];
                via[j][k] = via[i][k];}
            }
        }
    }
   
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            printf("%d ",(dv[i][j]>=987654321)?0:dv[i][j]);
        }
        printf("\n");
    }
   
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(via[i][j]==-1){
                printf("%d",0);
            }
            else{

                st.push(j);
                int pre = j;
                func(i,j);
                printf("%d ",st.size());
                while(st.size()){
                    printf("%d ",st.top());
                    st.pop();
                }
            }
            printf("\n");
        }
    }
    
    
}

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

문제

문제

출처

ICPC

플루이드워셜2 왜틀렸는지 잘모르겠어요!

qkrwjdfbf 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말