글 읽기 - ㅜㅜ 감사합니다. 해결했습니다.

dong_s 6년 전 0

우선 각 엣지들의 최소값을 행렬에 두고 워셜알고리즘을 수행시켰습니다.

그리고 다들 하시는 1-a-b-n / 1-b-a-n을 수행했구요.

기본 초기값이 212345로설정해서

세가지를 합했을때 int범위 초과도 아니고, 하나라도 길이 없는 경우 합은 212345를 넘을것이라 판단하여 출력구문을 작성하였습니다.

혹시 무엇이 문제인지 알수있을까요 ?

dong_s 6년 전 0

답변 감사합니다. :)

MAX최단거리로 INF를 선언 해주었고. 초기화를 했습니다.

또한

```

unsigned long long ans = INF;
if(arr[1][a] != INF || arr[a][b] != INF || arr[b][n] != INF)
ans = min(ans, arr[1][a] + arr[a][b] + arr[b][n]);
if(arr[1][b] != INF || arr[b][a] != INF || arr[a][n] != INF)
ans = min(ans, arr[1][b] + arr[b][a] + arr[a][n]);
printf("%d", ans == INF ? -1 : ans);

```

로 하나라도 다 이어질수 있는경우에 ans랑 min값을 비교하도록하였습니다.

그래도 오답이 나오는데 혹시 어디서 제가 더 틀렸는지 알수있을까요..??

감사합니다.

#include <cstdio>
unsigned long long arr[802][802];
#define min(r, l) r > l ? l : r
#define INF 212345678
int n, e, a, b, c;
int main() 
{
    scanf("%d %d", &n, &e);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            arr[i][j] = INF;

    for (int i = 0; i < e; ++i)
    {
        scanf("%d %d %d", &a, &b, &c);
        arr[a][b] = min(c, arr[a][b]);
        arr[b][a] = min(c, arr[b][a]);
    }
    for (int k = 1; k <=n ; ++k)
        for (int i = 1; i <= n; ++i)
            if(i != k)
                for (int j = 1; j <= n; ++j)
                    if(j != k && i != j)
                        arr[i][j] = min(arr[i][k] + arr[k][j], arr[i][j]);
    scanf("%d %d", &a, &b);
    unsigned long long ans = INF;
    if(arr[1][a] != INF || arr[a][b] != INF || arr[b][n] != INF)
        ans = min(ans, arr[1][a] + arr[a][b] + arr[b][n]);
    if(arr[1][b] != INF || arr[b][a] != INF || arr[a][n] != INF)
        ans = min(ans, arr[1][b] + arr[b][a] + arr[a][n]);
    printf("%d", ans == INF ? -1 : ans);
    return 0;
}

ehddml3 6년 전 1

4 6

1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
1 4

dong_s 6년 전 1

@ehddml3님 감사합니다.

자신을 찾아오는걸 고려안했었네요 ㅠㅠ

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

문제

문제

출처

ICPC

ㅜㅜ 감사합니다. 해결했습니다.

dong_s 6년 전 0

jh05013 6년 전 1

dong_s 6년 전 0

ehddml3 6년 전 1

dong_s 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말