글 읽기 - 100%에 틀립니다ㅠ

joehandlebar 6년 전 0

저도 start->u->v->end, start->v->u->end 방식대로 해봤어요~

#include <iostream>
#include <cstdio>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

int N, E;
long INF = 6223372036854775807;
long d[801];

void dijkstra(int i, vector<vector<pair<int,int>>> & adj) {
  priority_queue<int, vector<int>, greater<int>> q;

  fill_n(begin(d)+1, N, INF);
  d[i] = 0;
  q.push(i);

  while (!q.empty()) {
    int j = q.top();
    q.pop();
    vector<pair<int,int>> v = adj[j];

    auto it = v.begin();
    while (it != v.end()) {
      pair<int,int> p = *it;
      if (d[j] + p.second < d[p.first]) {
        d[p.first] = d[j] + p.second;
        q.push(p.first);
      }
      it++;
    }
  }
}

int main() {
  int u, v, w;
  vector<int> c;
  scanf("%d %d", &N, &E);

  vector<vector<pair<int,int>>> adj;
  adj.resize(N+1);

  for (int i = 0; i < E; i++) {
    scanf("%d %d %d", &u, &v, &w);
    adj[u].push_back(make_pair(v,w));
    adj[v].push_back(make_pair(u,w));
  }

  scanf("%d %d", &u, &v);

  long start_to_u, start_to_v, u_to_v, v_to_u,
       u_to_end, v_to_end;

  dijkstra(1, adj);
  start_to_u = d[u]; start_to_v = d[v];

  dijkstra(u, adj);
  u_to_v = d[v]; u_to_end = d[N];

  dijkstra(v, adj);
  v_to_u = d[u]; v_to_end = d[N];

  long result = min(start_to_u + u_to_v + v_to_end, start_to_v + v_to_u + u_to_end);

  cout << result << '\n';

  return 0;
}

chogahui05 6년 전 4

100%에서 틀렸다면 코너 케이스가 제대로 처리가 안 된 경우겠죠.. ㅠㅠ

이런 경우 어떻게 출력되나요?

joehandlebar 6년 전 0

아 ! 그런 경우도 있었네요, 감사합니다~

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

문제

문제

출처

ICPC

100%에 틀립니다ㅠ

joehandlebar 6년 전 0

chogahui05 6년 전 4

joehandlebar 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말