글 읽기 - 메모리 초과를 해결했더니 시간 초과가 나네요...

blackout 4년 전 0

전에 발생했던 메모리 초과 오류를 해결했는데,

이제는 시간 초과가 나네요...

왜 이럴까요?(+인접리스트 처음? 써봤습니다)

#include <bits/stdc++.h>
#define MAX 20010
#define INF 100000000
using namespace std;
typedef struct{
    int la,lb;
}line;
vector<line> grp[MAX];
int dst[MAX];
int visit[MAX];
int main()
{
    int n,m,k;
    scanf("%d %d",&n,&m);
    scanf("%d",&k);
    for(int i=1;i<=n;i++) dst[i]=INF;
    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        grp[u].push_back({v,w});
        if(u==k) dst[v]=w;
    }
    dst[k]=0;
    for(int i=1;i<n;i++){
        int sm=INF;
        int v=INF;
        for(int j=1;j<=n;j++){
            if(visit[j]==0 && sm>dst[j] && j!=k){
                sm=dst[j];
                v=j;
            }
        }
        if(v!=INF){
            visit[v]=1;
            for(int j=1;j<=grp[v].size();j++){
                if(grp[v][j-1].la!=v && grp[v][j-1].la!=k){
                    if(dst[grp[v][j-1].la]>dst[v]+grp[v][j-1].lb){
                        dst[grp[v][j-1].la]=dst[v]+grp[v][j-1].lb;
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dst[i]==INF) printf("INF\n");
        else printf("%d\n",dst[i]);
    }
    return 0;
}

djm03178 4년 전 0

지금과 같이 매번 모든 노드를 순회하면서 가장 거리가 가까운 노드를 뽑으려고 하면, n개의 노드를 n번 돌면서 하나씩 뽑아야 하니까 O(n^2)이 됩니다. 이 문제에서 정점의 수가 2만 개이기 때문에 애매하게 돌지 못할 수 있습니다.

우선순위 큐를 사용하는 방법에 대해 알아 보세요.

blackout 4년 전 0

알고리즘 분류에 다익스트라 알고리즘일고 나와있어서 써봤는데,그러면 다익스트라 알고리즘으로 풀 수 있는 거 아닌가요?

djm03178 4년 전 0

똑같은 다익스트라 알고리즘도 구현하는 방법이 여러 가지가 있고, 그 중 하나가 우선순위 큐를 쓰는 것입니다. 오히려 지금처럼 모든 노드를 순회하는 것보다도 더 일반적이고 가장 대표적인 다익스트라 구현 방법이라고 할 수 있습니다.

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

문제

문제

출처

ICPC

메모리 초과를 해결했더니 시간 초과가 나네요...

blackout 4년 전 0

djm03178 4년 전 0

blackout 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말