[SWEA] 5684 운동

 

사이클 중 가중치의 합이 가장 작은 사이클의 길이를 출력하는 문제다

N이 크면 다른방법을 쓰겠지만 N이 작아서 그냥 완탐을 돌렸다

 

모든정점에서 시작해서 해당 정점으로 돌아오는 사이클을 찾고 비교하면 된다

근데 이상하게 가지치기를 하니까 정답이고 안하니까 테케 3개가 틀린다

왜일까..! 가지치기 안해도 다시 시작점으로 돌아올 때 min값을 초기화하면 

답이 나올거라고 생각했는데..! 아직 의문이다

 

ans>sum+cost 이 부분을 빼면 틀린다..!

아시는분..!

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int t,n,m;
bool check[404];
const int inf = 1600000005;
int ans =inf;
void dfs(int now,int sum,int start,vector<vector<pair<int,int>>>& Graph){
    check[now]=true;
    for(int i=0;i<Graph[now].size();i++){
        int next = Graph[now][i].first;
        int cost = Graph[now][i].second;
        if(!check[next] && ans>sum+cost) dfs(next,sum+cost,start,Graph);
        if(start==next) ans = min(ans,sum+cost);
    }
}
int main(){
    scanf(" %d",&t);
    for(int tc=1;tc<=t;tc++){
        scanf(" %d %d",&n,&m); ans=inf;
        vector<vector<pair<int,int>>> Graph(n+1);
 
        for(int i=0;i<m;i++){
            int x,y,z; scanf(" %d %d %d",&x,&y,&z);
            Graph[x].push_back({y,z});
        }
        for(int i=1;i<=n;i++) {
            memset(check,0,sizeof(check));
            dfs(i,0,i,Graph);
        }
        if(ans==inf) ans=-1;
        printf("#%d %d\n",tc,ans);
    }
}