글 읽기 - 64%에서 시간 초과가 납니다.

rootsquare 3년 전 0

BFS 방식으로 그래프를 순회하는 방식을 사용하였으나 시간 초과가 납니다.

혹시 반복을 더 줄이는 방법이 있을까요?

#include<stdio.h>
#include<vector>
#include<queue>
#include<utility>
#define INF 1000000000
using namespace std;
typedef pair<int,int> PP;//도착 섬,중량제
queue<PP> Q;//큐
int smaller(int x,int y);//더 작은 값을 넣는 함수
int main(void)
{
    int island,roads;
    int si,gi,limit;
    int now_point,now_weight,tmp_point,tmp_weight,roll;
    vector<PP> maps[10010];//섬의 지도
    int answer[10010]={0};//시작 정점 기준 해당 섬까지 실을 수 있는 짐의 최댓값을 저장한다.
    scanf("%d %d",&island,&roads);//섬과 도로의 개수를 입력받는다.
    for(int i=1; i<=roads; i++)
    {
        scanf("%d %d %d",&si,&gi,&limit);//도로의 정보를 입력받고 벡터 배열에 해당 도로를 저장한다.
        maps[si].push_back(make_pair(gi,limit));
        maps[gi].push_back(make_pair(si,limit));
    }
    scanf("%d %d",&si,&gi);//시작,도착점을 설정한다.
    Q.push(make_pair(si,INF));//시작섬에서는 무한히 많은 짐을 실을 수 있으므로, 무한히 많은 짐을 실은 차를 큐에 넣는다.
    while(!Q.empty())//큐에 더 이상 남은 차가 없을 때까지 반복한다.
    {
        now_point=Q.front().first;//현재 차가 서 있는 섬
        now_weight=Q.front().second;//현재 차에 실려 있는 짐의 무게
        Q.pop();
        roll=maps[now_point].size();//현 섬으로부터 갈 수 있는 섬들을 찾는다.
        for(int i=0; i<roll; i++)
        {
            tmp_point=maps[now_point][i].first;//다음으로 갈 섬
            tmp_weight=smaller(now_weight,maps[now_point][i].second);//현재 실려있는 무게보다 해당 다리의 중량 제한이 낮을 경우 그 중량 제한만큼 짐을 덜어낸다.
            if(answer[tmp_point]<tmp_weight)//더 많은 짐을 보낼 수 있다면
            {//그 섬으로 차를 보낸다.
                Q.push(make_pair(tmp_point,tmp_weight));
                answer[tmp_point]=tmp_weight;
            }
        }
    }
    printf("%d",answer[gi]);//최종 정답을 출력한다.
    return 0;
}
int smaller(int x,int y)
{
    if(x>=y)
    {
        return y;
    }
    return x;
}

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

문제

문제

출처

ICPC

64%에서 시간 초과가 납니다.

rootsquare 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말