글 읽기 - 해당문제를 다익스트라 세번으로 정답을 구할 수 없습니까?

gaelim 6년 전 1

문제의 요구사항에는

1 ~ n 까지의 최단경로를 구하되 주어지는 두 점 p1, p2 을 반드시 거쳐가라고 해서

저는 그 세점 (1, p1, p2)를 루트로한 모든 정점으로의 shortest path tree를 생성해주면 될거라고 생각했습니다. 그래서 각 정점을 기준으로 dijkstra 알고리즘을 구현했습니다.

그래서 저는, 1에서 모든 정점으로의 최단거리 다익스트라를 통해 shortest path tree를 생성해 그 결과값을 d[0][1~n] 에 저장하였고

두번 째로 p1 에서 모든 정점으로의 최단거리를 또 다익스트라를 통해 d[1][1~n]에 저장하였고,

세번 째로 p2 에서 모든 정점으로의 최단거리를 또 다익스트라를 통해 d[2][1~n]에 저장하였습니다.

그 뒤 1 ~ n 를 갈수 있는 경로에서 p1, p2 를 지나갈 수 있는 경우의 수는

1 ~ p1 ~ p2 ~ n 과

1 ~ p2 ~ p1 ~ n 으로 서 distance 배열(vector)에서는

다음과 같이 참조되기에 ,

d[0][p1] + d[1][p2] + d[2][n]

d[0][p2] + d[2][p1] + d[1][n]

min으로 비교연산후 출력해주었습니다. 만 굉장히 낮은 퍼센티지(%)에서 WA를 맞습니다.

어디서부터 잘 못 된 논리인지 궁금합니다.

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
typedef struct{ int v, w; }node;
vector<node> e[801];
int d[3][801], pred[801];
priority_queue< pair<int, int> > pq;

int main(){
  int n, m; scanf("%d %d", &n, &m);
  while (m--){
    int u, v, w; scanf("%d %d %d", &u, &v, &w);
    e[u].push_back({v, w}); e[v].push_back({u, w});
  }

  int p1, p2; scanf("%d %d", &p1, &p2);

  for (int i=0; i< 3; i++)
    for (int j=1; j<=800; j++)
      d[i][j] = 3*800*1000+1;

  int a[3] = {1, p1, p2};

  for (int k=0; k<3; k++){
    pq.push( make_pair( 0, a[k]) );
    d[k][a[k]]=0;

    while(!pq.empty()){

      int cost = -pq.top().first;
      int now = pq.top().second;
      pq.pop();

      if ( d[k][now] < cost) continue;

      for (int i=0; i<e[now].size(); i++){

        if ( d[k][e[now][i].v] >  d[k][now] + e[now][i].w ){
          d[k][e[now][i].v] = d[k][now] + e[now][i].w;
          pq.push(make_pair(-d[k][e[now][i].v], e[now][i].v));
        }
      }
    }
  }
  int ans=min(d[0][p1]+d[1][p2]+d[2][n] , d[0][p2]+d[2][p1]+d[1][n]);
  printf("%d\n", (ans>=3*800*1000+1)?-1:ans);
}

ntopia 6년 전 1

전 이 소스 그대로 제출했더니 맞았어요.

아주 가끔 올바른 답안을 틀렸다고 할 때가 있는데 (boj 버그)

그 버그가 발생한 것 같아요.

jh05013 6년 전 1

마지막으로 제출하신 코드에 오타가 있습니다.

d[0][E]+d[2][E]+d[1][n]

gaelim 6년 전 0

버그와, 오타 문제였군요 감사합니다!!!

gaelim 6년 전 0

아 죄송합니다

버그가 아니라 제가 마지막에 제출한게 오타가있었군요. 질문할 때는 같다고 생각하고 변수명만

S, E를 p1, p2로 바꾸는 과정에서 오타가 수정돼서 질문을했습니다.

죄송합니다... 이 오해가 풀리지 않았으면 혼자서 다익스트라에 대한 새로운 정의를 내릴뻔했네요.

감사합니다.

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

문제

문제

출처

ICPC

해당문제를 다익스트라 세번으로 정답을 구할 수 없습니까?

gaelim 6년 전 1

ntopia 6년 전 1

jh05013 6년 전 1

gaelim 6년 전 0

gaelim 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말