글 읽기 - 어디가 틀렸는지 모르겠어요...

vhxpffltm 7년 전 0

백트랙 해서 체크하고 하면서 했는데 답이 안나오네요...ㅠ

7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40
1 7

이 예제는 잘 나오는데 문제예제가 안나와서 도움좀 부탁드립니다

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#pragma warning(disable:4996)

using namespace std;
long long V,G,n, m, arr[110][110] = { 0 }, chk[10001] = { 0 }, ans = 100001;
void sol(int v, int w)
{//v : 시작정점    w : 가중치 값
	//if (w > ans) return;
	if (v == V)
	{
		if (w <= ans) ans = w;
		return;
	}
	for (int i = n; i <= m; i++)
		if (!chk[i] && arr[v][i])
		{
			chk[i] = 1;
			sol(i, w + arr[v][i]);
			chk[i] = 0;
		}//백트래킹,전체 탐색
}
int main()
{
	cin >> V;
	cin >> G;
	for (int i = 0; i < G; i++) {
		int s, e, g;
		scanf("%d %d %d", &s, &e, &g);
		arr[s][e] = arr[e][s] = g;
	}
	scanf("%d %d", &n, &m);
	sol(n,0);
	printf("%d\n", ans==100001 ? -1 : ans);
}

ainch96 7년 전 0

이 문제는 최악의 경우 시간 복잡도가 너무 커서 백트래킹으로 풀 수 없습니다.

다른 알고리즘이 필요합니다.

Dijkstra 알고리즘을 공부해 보시기 바랍니다.

그리고 sol 함수의 for 문에서

모든 정점과 연결 되어 있는지 확인 해야 하기 때문에

for(i=n;i<=m;++i) 가 아니라 for(i=1;i<=V;++i)으로 해야 합니다.

그리고 ans값을 처음에 10001으로 하면 안됩니다. 비용이 범위가 [0,100000]이고 정점이 [1,1000] 이라서

최악의 경우 거리가 거의 1000000000 이기 때문입니다.

ainch96 7년 전 0

그리고 이 그래프는 양방향성이 아니라 단방향 성이기 때문에

arr[s][e] = g;

입니다.

arr[s][e] = arr[e][s] = g;

가 아닙니다.

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#pragma warning(disable:4996)
 
using namespace std;
long long V,G,n, m, arr[110][110] = { 0 }, chk[10001] = { 0 }, ans = 100001;
void sol(int v, int w)
{//v : 시작정점    w : 가중치 값
    //if (w > ans) return;
    if (v == V)
    {
        if (w <= ans) ans = w;
        return;
    }
    for (int i = n; i <= m; i++)
        if (!chk[i] && arr[v][i])
        {
            chk[i] = 1;
            sol(i, w + arr[v][i]);
            chk[i] = 0;
        }//백트래킹,전체 탐색
}
int main()
{
    cin >> V;
    cin >> G;
    for (int i = 0; i < G; i++) {
        int s, e, g;
        scanf("%d %d %d", &s, &e, &g);
        arr[s][e] = g;
    }
    scanf("%d %d", &n, &m);
    sol(n,0);
    printf("%d\n", ans==100001 ? -1 : ans);
}

vhxpffltm 7년 전 0

좋은 말씀 감사합니다~~ 다익스트라 공부해서 해 볼께요~~

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

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠어요...

vhxpffltm 7년 전 0

ainch96 7년 전 0

ainch96 7년 전 0

vhxpffltm 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말