[백준 1504] 특정한 최단 경로

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

다익스트라를 사용해서 노드 간의 거리를 구해준다. v1과 v2를 무조건 지나야 하므로 

1 -> v1 -> v2 -> last

1 -> v2 -> v1 -> last 사이의 거리를 비교하여 작은 값을 리턴해준다.

양방향 그래프이고 비용이 같으므로 v1-> v2 == v2 -> v1이다.

따라서 사이 값을 mid로 한번만 구한다.

 

다익스트라 특성상 하나의 출발지로부터 모든 노드로의 최단 거리를 구하므로 목적지가 어딘지는 상관없고...출발지만 정해준 다음에 목적지까지의 dis를 구한다. 

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 1e9
#define ll long long

using namespace std;
int n, e, v1, v2;
ll dis[801];

vector<pair<int, int>> v[801];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
void dijkstra(int src)
{
  for (int i = 1; i <= n; i++)
  {
    dis[i] = INF;
  }

  dis[src] = 0;
  pq.push(make_pair(0, src));

  while (!pq.empty())
  {
    ll ccost = pq.top().first;
    int cv = pq.top().second;

    pq.pop();

    for (auto a : v[cv])
    {
      ll ncost = a.first;
      int nv = a.second;

      if (dis[nv] > ccost + ncost)
      {
        dis[nv] = ccost + ncost;
        pq.push(make_pair(dis[nv], nv));
      }
    }
  }
}

int main(void)
{
  scanf("%d%d", &n, &e);
  for (int i = 0; i < e; i++)
  {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    v[a].push_back(make_pair(c, b));
    v[b].push_back(make_pair(c, a));
  }
  scanf("%d%d", &v1, &v2);

  bool flag1 = true, flag2 = true;
  dijkstra(1);

  ll one_v1 = dis[v1];
  ll one_v2 = dis[v2];

  if (one_v1 == INF)
    flag1 = false;
  if (one_v2 == INF)
    flag2 = false;

  //v1과 v2 사이
  //v1 to last
  dijkstra(v1);
  ll mid = dis[v2];
  ll v1_last = dis[n];

  if (mid == INF)
  {
    flag1 = false, flag2 = false;
  }

  if (v1_last == INF)
  {
    flag2 = false;
  }
  //v2 to last
  dijkstra(v2);
  ll v2_last = dis[n];
  if (v2_last == INF)
  {
    flag1 = false;
  }

  ll res1 = one_v1 + mid + v2_last, res2 = one_v2 + mid + v1_last;
  if (!flag1 && !flag2)
  {
    printf("-1\n");
  }
  else if (flag1 && flag2)
  {
    printf("%lld\n", res1 > res2 ? res2 : res1);
  }
  else
  {
    if (flag2)
    {
      printf("%lld\n", res2);
    }
    else
    {
      printf("%lld\n", res1);
    }
  }

  return 0;
}