글 읽기 - 시간초과 문의합니다.

zmfldlwl 8년 전 0

플로이드 와셜로는 통과가 되던데, 다익스트라 들어가니까 통과가 안되네요..

둘다 같은 시간복잡도를 가지고 있는거 같은데... O(n^3)으로요.

#include <stdio.h>
#include <memory.h>

#define N 1000
#define INF 100000

int a[N + 1][N + 1];
int visit[N + 1];
int dist[N + 1];
int dist2[N + 1];
int rr[N + 1];
int n, m, x;

void input()
{
    int from, to;
    int w;
    scanf("%d", &n);
    scanf("%d", &m);
    scanf("%d", &x);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i != j)
                a[i][j] = INF;
        }
    }

    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &from, &to, &w);
        a[from][to] = w;
    }

    for (int i = 1; i <= n; i++)
        dist[i] = INF;
}

void init()
{
    for (int i = 1; i <= n; i++)
        dist[i] = INF;

    memset(visit, 0, sizeof(visit));
}

//a -> start, b -> end
void dijkstra(int x)
{
    int i, j;
    int min = INF;
    int v;

    dist[x] = 0;

    for (int i = 1; i <= n; i++)
    {
        min = INF;

        for (int j = 1; j <= n; j++)
        {
            if (visit[j] == 0 && min > dist[j])
            {
                min = dist[j];
                v = j;
            }
        }

        visit[v] = 1;

        if (min == INF)
            continue;

        for (int j = 1; j <= n; j++)
        {
            if (a[v][j] == INF)
                continue;

            if (dist[j] > dist[v] + a[v][j])
                dist[j] = dist[v] + a[v][j];
        }
    }
}

int main()
{
    input();

    int r_max = -2100000000;
    int res;
    int loc;

    init();
    dijkstra(x);

    for (int i = 1; i <= n; i++)
        dist2[i] = dist[i];

    for (int i = 1; i <= n; i++)
    {
        init();
        dijkstra(i);

        dist2[i] += dist[x];

        if (dist2[i] > r_max)
            r_max = dist2[i];
    }

    printf("%d\n", r_max);

    return 0;
}

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

문제

문제

출처

ICPC

시간초과 문의합니다.

zmfldlwl 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말