글 읽기 - 시간 초과 문제 해결에 관한 조언 부탁드리겠습니다.(c++)

Rose 5년 전 0

제가 생각한 알고리즘은 BFS+DP로 n도시로 가는 최대 기내식 점수를 구하는 알고리즘입니다.

d[i][j]=i도시까지 여행하는데 출발점과 자기를 합쳐서 j개의 도시를 거처 온 최대 기내식 만족도

큐에 1번정점부터 넣어줍니다.
자기보다 큰 정점으로 가는 현재 최댓값이 현재 점수+ 현재정점에서 그 정점으로 가는 값 보다 작다면 갱신해줍니다.
마지막에 Max(d[n][1~m])을 구해줍니다

혹시 제 알고리즘이 고려 못한 점이 있거나 시간초과를 야기할만한것이 있다면 조언 부탁드리겠습니다.

//d[i][j]=i도시까지 여행하는데 출발점과 자기 합쳐 j개의 도시를 거쳐 온 최대 기내식 만족도
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
struct way{
    int city,many,full;//도시 번호, 이때까지 몇개 탔는지, 기내식 점수
};
queue<way> q;
vector<pair<int,int> >v[304];//first:정점, second:기내식 맛
int d[304][304];
int path[304][304];//중복간선 방지 위해 한정점에서 다른정점으로 가는 최댓값만 저장
int Max(int a,int b){ return (a<b)?b:a; }
int M;
int main(){
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    for(int i=0;i<k;i++){
        int s,e,val;
        scanf("%d %d %d",&s,&e,&val);
        if(s<e){
            path[s][e]=Max(path[s][e],val);
        }
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(path[i][j])
                v[i].push_back({j,path[i][j]});
        }
    }
    q.push({1,1,0});
    while(!q.empty()){
        int x=q.front().city,y=q.front().many,z=q.front().full;
        q.pop();
        for(int i=0;i<v[x].size();i++){
            if(y+1<=m&&d[v[x][i].first][y+1]<z+v[x][i].second){
                d[v[x][i].first][y+1]=z+v[x][i].second;
                q.push({v[x][i].first,y+1,z+v[x][i].second});
            }
        }
    }
    for(int i=1;i<=m;i++){
        M=Max(M,d[n][i]);
    }
    printf("%d",M);
    return 0;
}

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

문제

문제

출처

ICPC

시간 초과 문제 해결에 관한 조언 부탁드리겠습니다.(c++)

Rose 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말