글 읽기 - 1504 특정한 경로 찾기 반례를 못찾겠습니다..

qqwq9999 6년 전 0

다익스트라로 해결한 코드입니다.

다음과 같이 해결하려합니다.

거쳐야할 노드1 : A, 거쳐야할 노드2: B

최소비용(출발점->A) + 최소비용(A->B) + 최소비용(B->목적지)

VS

최소비용(출발점->B) + 최소비용(B->A) + 최소비용(A->목적지)

처음에 44번 라인의 주석을 해제하고 제출 했습니다.

99% 때 틀렸습니다 가 나왔습니다.

44번 라인이 있어도 무방하다고 생각했는데, 도저히 반례를 찾을 수가 없습니다..

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

using namespace std;

typedef long long ll;

class CompareCost{
public:
    bool operator()(pair<int, ll> n1, pair<int, ll> n2){
      return n1.second > n2.second;
    }
};

const int INF = 800001;
vector <pair <int, ll> > edges[801];
priority_queue <int, vector<int>, greater<ll> > mustPass;

bool isVisited[801];
ll dist[801];
int N;

void dijkstra(int start, int dst){

  fill_n(dist, N+1, INF);
  fill_n(isVisited, N+1, false);
  dist[start] = 0;

  priority_queue <pair <int, int>, vector <pair <int, int> >, CompareCost> pq;

  pq.push(make_pair(start, dist[start]));

  while(!pq.empty()){
    int current;

    do {
      current = pq.top().first;
      pq.pop();
    }while(!pq.empty() && isVisited[current]);

    // if(current == dst) return;

    isVisited[current] = true;

    for(int i = 0; i<edges[current].size(); i++){
      int to    = edges[current][i].first;
      ll cost   = edges[current][i].second;

      if(dist[to] > dist[current] + cost){
        dist[to] = dist[current] + cost;
        pq.push(make_pair(to, dist[to]));
      }
    }
  }
}

int main() {

  int M, mustPassArr[2];
  ll result1 = 0, result2 = 0;

  scanf("%d %d", &N, &M);

  for(int i = 0; i<M; i++){
    int from, to, cost;
    scanf("%d %d %d", &from, &to, &cost);
    edges[from].push_back(make_pair(to, cost));
    edges[to].push_back(make_pair(from, cost));
  }

  scanf("%d %d", &mustPassArr[0], &mustPassArr[1]);

  for (int i=0; i<2; i++) mustPass.push(mustPassArr[i]);

//  ll between = dijkstra(mustPassArr[0], mustPassArr[1]);
  dijkstra(1, mustPassArr[0]);
  result1 += dist[mustPassArr[0]];

  dijkstra(mustPassArr[0], mustPassArr[1]);
  result1 += dist[mustPassArr[1]];

  dijkstra(mustPassArr[1], N);
  result1 += dist[N];

  dijkstra(1, mustPassArr[1]);
  result2 += dist[mustPassArr[1]];

  dijkstra(mustPassArr[1], mustPassArr[0]);
  result2 += dist[mustPassArr[0]];

  dijkstra(mustPassArr[0], N);
  result2 += dist[N];

  ll result = min(result1, result2);

  if(result >= INF)printf("-1\n");
  else{
    printf("%lld\n", result);
  }

  return 0;
}

alibaba 6년 전 0

경로를 찾아 가는 중에 못가는 경우가 나옴니다. -1 처리를 더하기 전부터 해주시면 될거 같습니다.

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

문제

문제

출처

ICPC

1504 특정한 경로 찾기 반례를 못찾겠습니다..

qqwq9999 6년 전 0

alibaba 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말