글 읽기 - 어디서 시간 초과가 나는지 알수 있을까요??

ljk0411jg 7년 전 0

처음에 다익스트라로 최단거리를 구해서 dist배열에 저장하고 dfs 돌려서 마지막 노드의 카운터가 최단거리 길이와 같으면 그 간선들을 제거해주고 마지막으로 한번더 다익스트라를 돌려서 답을 구하는 구조입니다. 어디서 자꾸 시간초과가 나는지 궁금합니다. 도와주시면 감사하겠습니당 >,.<

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef struct _data
{
  int weight;
  int node;
}Data;
vector<Data>vec[505];
int deleteline[505][505], chk[505][505];
int dist[505], Min;

int deletenode(int start, int end, int count, int parentnode)
{
  int temp = 0;
  if(start == end && dist[end] == count)
  {
    return 1;
  }
  for(int i = 0; i < vec[start].size(); i++)
  {
    int a = 0;
    if(chk[start][vec[start][i].node] == 0 && vec[start][i].node != parentnode)
    {
      chk[start][vec[start][i].node] = 1;
      deleteline[start][vec[start][i].node] = 1;
      a = deletenode(vec[start][i].node, end, count + vec[start][i].weight, parentnode);
      chk[start][vec[start][i].node] = 0;
      if(a == 1)
      {
        temp = a;
      }
      if(a == 0)
      {
        deleteline[start][vec[start][i].node] = 0;
      }
    }
  }
  return temp;
}

int BFS(int start, int end)
{
  queue<Data>q;
  q.push({0, start});
  dist[start] = 0;
  while(!q.empty())
  {
    Data temp;
    temp = q.front();
    q.pop();
    if(dist[temp.node] < temp.weight)
    {
      continue;
    }
    if(temp.node == end)
    {
      Min = dist[temp.node];
      break;
    }
    for(int i = 0; i < vec[temp.node].size(); i++)
    {
      Data next;
      next.node = vec[temp.node][i].node;
      next.weight = vec[temp.node][i].weight;
      if(dist[next.node] > dist[temp.node] + next.weight && deleteline[temp.node][next.node] == 0)
      {
        dist[next.node] = dist[temp.node] + next.weight;
        q.push(next);
      }
    }
  }
}

int main()
{
  while(1)
  {
    memset(vec, 0, sizeof vec);
    int N, M, S, D;
    scanf("%d %d", &N, &M);
    if(N == 0 && M == 0)
    {
      break;
    }
    scanf("%d %d", &S, &D);
    for(int i = 0; i < M; i++)
    {
      int U, V, P;
      scanf("%d %d %d", &U, &V, &P);
      vec[U].push_back({P, V});
    }
    Min = 0;
    memset(deleteline, 0, sizeof deleteline);
    memset(dist, 0x3f, sizeof dist);
    BFS(S, D);
    Min = 0;
    deletenode(S, D, 0, S);
    memset(dist, 0x3f, sizeof dist);
    BFS(S, D);
    if(Min == 0)
    {
      printf("-1\n");
    }
    else
    {
      printf("%d\n", Min);
    }
  }
}

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

문제

문제

출처

ICPC

어디서 시간 초과가 나는지 알수 있을까요??

ljk0411jg 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말