글 읽기 - 반례좀 알려주세요!(100% 에서 틀림)

112224 5년 전 0

첫번째 다익스트라로 s->e의 최단거리를 구함+최단거리로 오는 경로들 저장

두번째 다익스트라를 하면서 방문하지 않은 지점이 최단거리의 경로가 아니면 갱신

다음 지점이 e일경우에는 거리가 최단거리가 아니여야 갱신.

제 생각엔 문제가 없는 것 같은데...

반례나 문제가 되는 부분을 알려주시면 감사하겠습니다.

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,int> ii;

int dist[501];
bool visit[501];

int n,m;

void find(vector<int> a[],int prev)
{
    
    int tmp;
    for(auto it=a[prev].begin();it!=a[prev].end();++it)
    {
        tmp=*it;
        if(visit[tmp])
        continue;
        visit[tmp]=true;
        find(a,tmp);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    
    for(int n,m;cin>>n>>m;)
    {
        if(n==0&&m==0)
        break;
        int s,e;
        cin>>s>>e;
        vector<ii> a[501];
        vector<int> prev[501];
        
        while(m--)
        {
            int x,y,z;
            cin>>x>>y>>z;
            a[x].push_back({z,y});
        }
        fill_n(visit,n+1,false);
        fill_n(dist,n+1,987654321);
        if(a[s].size()==1)
        {
            cout<<"-1\n";
            continue;
        }
        priority_queue<ii,vector<ii>,greater<ii> >pq;   //first=노드까지의 거리(dist[secnd]),second=node
        dist[s]=0;
        pq.push({0,s});
        while(!pq.empty())
        {
            int d=pq.top().first;
            int now=pq.top().second;
            pq.pop();
            for(int i=0;i<a[now].size();i++)
            {
                ii next=a[now][i];
                int nn=next.second;
                
                if(dist[nn]>dist[now]+next.first)
                {
                    prev[nn].clear();                //최단거리가 바뀐 경우엔 기존 벡터 클리어.
                    prev[nn].push_back(now);
                    dist[nn]=dist[now]+next.first;
                    pq.push({dist[nn],next.second});
                }
                else if(dist[nn]==dist[now]+next.first)
                prev[nn].push_back(now);            //기존과 같으면 추가
                
            }
        }
        
        int mret=dist[e];
        if(mret==987654321)
        {
            cout<<"-1\n";
            continue;
        }
        find(prev,e);                        //vector prev[]를 이용해 visit 배열 설정.
    
        fill_n(dist,n+1,987654321);
        dist[s]=0;
        pq.push({0,s});
        while(!pq.empty())
        {
            int d=pq.top().first;
            int now=pq.top().second;
            pq.pop();
            for(int i=0;i<a[now].size();i++)
            {
                ii next=a[now][i];
                int nn=next.second;
                if(visit[nn])                                //최단거리를 이루는 경로이면 다음으로.
                continue;
                if(dist[nn]>dist[now]+next.first)
                {
                    if(nn==e&&dist[now]+next.first==mret)    //최종 도착지점일 때, 거리가 기존 최단거리면 갱신 x
                    continue;
                    dist[nn]=dist[now]+next.first;
                    pq.push({dist[nn],next.second});
                }
                
            }
        }
            
        if(dist[e]!=987654321)
        cout<<dist[e]<<'\n';
        else
        cout<<"-1\n";
    
    }
    
}

hu8232 3년 전 1

저도 100%에서 틀렸습니다가 나오는데 혹시 틀린 이유가 뭐였는지 알려주실 수 있으신가요?

112224 3년 전 0

근래 백준을 잘 못봐서요 ㅠㅠ 해결하셔서 다행입니다 :)

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

문제

문제

출처

ICPC

반례좀 알려주세요!(100% 에서 틀림)

112224 5년 전 0

hu8232 3년 전 1

112224 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말