글 읽기 - 시간초과 관련 질문합니다.(코드 주석 있음)

rootsquare 3년 전 0

벨만-포드 알고리즘을 이용하여 각 지점들을 각각 출발점으로 잡아서 최단거리를 구한 후 음수사이클이 있거나 출발점으로 돌아왔을 때 시간이 거꾸로 돌아갔으면 YES를 출력하는 방식으로 코드를 작성했는데 90%에서 시간 초과가 나왔습니다.

무엇이 문제일까요?

#include<stdio.h>
#include<vector>
#include<utility>
#define INF 10000000000000000
#define NO_EXIST 100000000
using namespace std;
typedef pair<int,int> PP;
void clear(long long distance[],int num);//최단거리를 저장하는 배열을 초기화한다.
long long smaller(long long x,long long y,int *changed);
int search_loop(vector<PP> bus[],long long distance[],int num);//벨만-포드 알고리즘
int main(void)
{
    int test,city,roads,wormholes,i,j,k,yes=0;
    int si,gi,length,check;
    vector<PP> bus[510];//길의 정보를 저장하는 벡터
    long long distance[510];//최단거리를 저장하는 배열
    int changed=0;
    scanf("%d",&test);//테스트 케이스의 수를 입력받는다.
    for(k=1; k<=test; k++)
    {
        yes=0;//되돌아 오는 것이 가능한지에 대한 여부. 1=가능/0=불가능
        scanf("%d %d %d",&city,&roads,&wormholes);//도시,도로,웜홀의 수를 입력받는다.
        for(i=1; i<=roads; i++)//도로들의 정보를 입력받는다.
        {
            scanf("%d %d %d",&si,&gi,&length);
            bus[si].push_back(make_pair(gi,length));
            bus[gi].push_back(make_pair(si,length));
        }
        for(i=1; i<=wormholes; i++)//웜홀들의 정보를 입력받는다.
        {
            scanf("%d %d %d",&si,&gi,&length);
            bus[si].push_back(make_pair(gi,length*(-1)));//웜홀은 시간이 거꾸로 가니 마이너스 길이로 만든다.
        }
        for(j=1; j<=city; j++)//각각의 도시를 출발점으로 잡고 벨만-포드 알고리즘을 수행한다.
        {
            clear(distance,city);//최단거리 배열을 초기화한다.
            distance[j]=0;//시작점의 거리는 0으로 만든다.
            for(i=1; i<=city; i++)
            {
                check=search_loop(bus,distance,city);//벨만-포드 알고리즘을 사용한다. 만일 최단거리가 하나라도 갱신될 경우 check=1, 아니면 check=0
            }
            if(check==1 || distance[j]<0)//만일 음수사이클이 존재하거나 시작지점으로 돌아올 수 있다면
            {
                yes=1;//돌아올 수 있다.
                break;
            }
        }
        yes==1 ? printf("YES\n") : printf("NO\n");//최종 정답을 출력한다.
        for(i=1; i<=city; i++)//도로와 웜홀의 정보를 초기화한다.
        {
            bus[i].clear();
        }
    }
    return 0;
}
void clear(long long distance[],int num)//최단거리 배열을 초기화
{
    int i;
    for(i=1; i<=num; i++)
    {
        distance[i]=INF;
    }
}
long long smaller(long long x,long long y,int *changed)
{
    if(x>y)
    {
        *changed=1;
        return y;
    }
    return x;
}
int search_loop(vector<PP> bus[],long long distance[],int num)//벨만-포드 알고리즘 사용
{
    int i,j,roll,changed=0;
    for(i=1; i<=num; i++)
    {
        roll=bus[i].size();
        for(j=0; j<roll; j++)//간선을 조사할 때, 섬으로 고립된 지역은 제외한다(없는 길이나 아직 도착도 안한 지점에서 시작은 조사하지 않는다)
        {
            if(distance[i]!=INF)
            {
                distance[bus[i][j].first]=smaller(distance[bus[i][j].first],distance[i]+bus[i][j].second,&changed);
            }
        }
    }
    return changed;//만일 최단거리 배열이 한 번이라도 수정되었으면 1, 아니면 0을 반환한다.
}

rootsquare 3년 전 0

그래프의 시작점에 관계없이 음의 사이클만 존재하면 다 OK군요. 그렇게 수정하였더니 해결했습니다.

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

문제

문제

출처

ICPC

시간초과 관련 질문합니다.(코드 주석 있음)

rootsquare 3년 전 0

rootsquare 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말