글 읽기 - 충분히 최단경로 문제로 풀릴것 같지만 풀리지 않습니다. 무엇이 문제인가요?

gaelim 6년 전 0

분류가 MCMF로 되어있기에 그런 템플릿으로 문제를 풀어보았습니다.

하지만 문제에서 요구하듯이 최단경로 와 그 다음 최단경로를 구하라는 것에서

그 다음 최단경로를 찾는 문제 successive shortestpath problem(?) 인것 같았고 그렇기에 다음과 같이 접근해보았습니다.

우선 다익스트라를 이용해 최단경로를 구해서 결과값을 ans 변수에 저장하고 .

해당 최단 경로를 정보를 도착지에서부터 역으로 이동해가면서 간선 가중치를 -1 로 만들어주었습니다. (그 반대방향 간선도 rev 라는 포인터 구조체 변수를 이용해 -1로 만들어 주었습니다)

그 뒤 다시 다익스트라를 이용해 1 에서 n 까지으 ㅣ최단경로를 구해주었습니다. 두 번 쨰 다익스트라에서는 간선의 가중치가 0 이하이면 간선을 무시하게했습니다.

이렇게 다익스트라를 돌린뒤에

그뒤 ans 변수와 d[n] 의 합을 출력해주었습니다.... 만 틀렸습니다가 떴습니다.

어떤것이 문제인가요? 아래는 소스입니다.

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

using namespace std;

struct Edge{
  int v, d;
  Edge* rev;
  Edge(int v, int d) : v(v), d(d) {}
};

int main(){
  int n, m; scanf("%d %d", &n, &m);
  vector<int> d(n+1);
  vector<pair<int, int> > pred(n+1);
  vector<vector<Edge*> > e(n+1);

  while(m--){
    int u, v, d; scanf("%d %d %d", &u, &v, &d);
    Edge* edge = new Edge(v, d);
    Edge* revedge = new Edge(u, d);
    edge->rev = revedge;
    revedge->rev = edge;
    e[u].push_back(edge);
    e[v].push_back(revedge);
  }

  priority_queue<pair<int, int> > pq;

  fill(d.begin(), d.end(), 0x3f3f3f3f);
  fill(pred.begin(), pred.end(), make_pair(-1, -1));
  pq.push(make_pair(0, 1));
  d[1]=0;

  while(!pq.empty()){
    int cost = -pq.top().first;
    int now = pq.top().second;
    pq.pop();
    for (int i=0; i<e[now].size(); i++){
      int v = e[now][i]->v, dist = e[now][i]->d;

      if (d[v] > d[now] + dist){
        d[v] = d[now]+dist;
        pred[v] = make_pair(now, i);
        pq.push(make_pair(-d[v], v));
      }
    }
  }

  int now = n;
  int ans = d[n];
  while(pred[now].first!=-1){
    e[pred[now].first][pred[now].second]->d=-1;
    e[pred[now].first][pred[now].second]->rev->d=-1;
    now = pred[now].first;
  }

  fill(d.begin(), d.end(), 0x3f3f3f3f);
  pq.push(make_pair(0, 1));

  d[1]=0;
  while(!pq.empty()){
    int cost = -pq.top().first;
    int now = pq.top().second;
    pq.pop();

    if ( d[now] <cost ) continue;

    for (int i=0; i<e[now].size(); i++){
      int v = e[now][i]->v, dist = e[now][i]->d;
      if (dist<0) continue;

      if (d[v] > d[now] + dist){
        d[v] = d[now]+dist;
        pq.push(make_pair(-d[v], v));
      }
    }
  }

  printf("%d\n", ans +d[n]);
}

kks227 6년 전 2

4 5

1 2 1

2 3 1

3 4 1

1 3 10

2 4 10

이런 그래프가 있으면, 왕복 경로를 찾지 못합니다.

gaelim 6년 전 0

@kks227 아 감사합니다...

위와 같은 예제는 애초에 처음부터 최단경로로 경로를 빌딩하면 두번 째 최단경로를 만들 수 없는경우군요..

아.... 감사합니다..

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