TPATH 문제 질문드립니다.

  • WeissBlume
    WeissBlume

    안녕하세요
    알고스팟 가입하고 처음 쓰는 글이네요 ㅎㅎ
    앞으로 잘부탁드립니다!

    문제 링크 : TPATH

    저는 이 문제를 세 가지 방법으로 생각해봤습니다.
    1. DFS로 모든 경로를 탐색해서 최소 차이를 구함.
    2. BFS로 모든 경로를 탐색해서 최소 차이를 구함.
    3. 바이너리 서치로 차이를 고정시키고 각각의 차이에 대해
    0번에서 N-1번으로 갈 수 있는지 BFS를 이용하여 체크.

    그런데 결과는..
    1. TLE
    2. TLE
    3. WA
    네요..
    1번과 2번이 안되는건 그럴만 한데,
    3번이 TLE도 아니고 WA가 나오는 이유를 모르겠어요ㅠㅠ

    코드 첨부합니다!

    #include<cstdio>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<cstdlib>
    using namespace std;
    typedef struct edge{
        int v,w,w2;
        edge(int a,int b){v=a;w=b;}
        edge(int a,int b,int c){v=a;w=b;w2=c;}
    //state로 사용할 때, w는 최소 속도, w2는 최대 속도를 저장
        edge(){}
    } state;
    int V;
    bool valid(vector<edge> adj[2001],int limit){
        for(int i=0;i<adj[0].size();i++){
            bool chk[2001]={false};
            queue<state>q;
            chk[0]=chk[adj[0][i].v]=true;
            q.push(state(adj[0][i].v,adj[0][i].w,adj[0][i].w));
            while(!q.empty()){
                state here=q.front();q.pop();
                if(here.w2-here.w>limit)continue;
                else if(here.v==V-1&&here.w2-here.w<=limit)return true;
                for(int j=0;j<adj[here.v].size();j++){
                    state there=adj[here.v][j];
                    if(!chk[there.v]){
                        chk[there.v]=true;
                        q.push(state(there.v,min(here.w,there.w),max(here.w2,there.w)));
                    }
                }
            }
        }
        return false;
    }
    int main(){
        int T;
        for(scanf("%d",&T);T--;){
            int E,i,j,k;
            scanf("%d%d",&V,&E);
            vector<edge> adj[2001];
            while(E--){
                scanf("%d%d%d",&i,&j,&k);
                adj[i].push_back(edge(j,k));
                adj[j].push_back(edge(i,k));
            }
            int L=0,R=2000,ans=1000;
            while(L<=R){
                int M=(L+R)/2;
                if(valid(adj,M)){ans=min(ans,M);R=M-1;}
                else L=M+1;
            }
            printf("%d\n",ans);
        }
        return 0;
    }
    

    아 그리고, 문제 설명에 오타가 하나 있어요
    "N줄에 각 3개의 정수로 운행 구간의 정보가 주어진다."
    라고 되어있는데, M개의 줄이어야 할 것 같아요.


    10년 전
4개의 댓글이 있습니다.
  • Being
    Being

    제보 감사합니다 :)

    솔루션에 대해서 한 마디 하자면, 이분검색을 사용하는 전략은 유효합니다만 차이를 고정하면 문제가 됩니다. 최단경로 알고리즘은 어떤 특정한 값을 최소화하는 방향으로 동작하는데, 한 노드가 두 값의 쌍을 가지게 되면 모든 전제가 무너집니다. 이를테면, 한 노드에 최대값과 최소값의 차이가 10이 되는 여러 방법이 있을 수 있는데 그것들을 모두 고려할 수 없습니다.


    10년 전 link
  • WeissBlume
    WeissBlume

    으 최단경로는 안 썼지만..
    다시 생각해봐야겠네요 ㅠㅠ감사합니다!


    10년 전 link
  • Being
    Being

    웁스 ㅋㅋ 설명을 조금 잘못 썼는데 의도했던 바는 알아들으셨으리라 생각합니다 ㅋㅋ


    10년 전 link
  • WeissBlume
    WeissBlume

    넵 ㅋㅋ!


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.