글 읽기 - 7141번 T 질문

joonas 9년 전 0

T가 정확히 2222개여야하나요?

107개는 몇개 안되서 숫자 갯수 딱 맞췄는데. 2222개는 안 맞췄더니 틀렸다고 하네요.

pichulia 9년 전 0

정확히 2222개일 필요는 없습니다.ㅠㅠ

joonas 9년 전 1

감사합니다. ㅋㅋ근데 오답이 맞네요. 결과가 반대로 뜨네요 쓰읍.ㅋㅋ

joonas 9년 전 0

죄송한데 자꾸 틀렸습니다를 받아서 질문드립니다.

두 알고리즘의 시간복잡도를 구했을 때 간선만 엄청나게 많아지면 플로이드가 더 빠를거라 생각했는데, 혹시 잘못된 생각인가요?

감사합니다.

int main(){
    // A : O(V^2 + VE + V^3 + Q)
    // B : O(V^2E + QV^2E )
    // if V<E : O(A) < O(B)
	int i, j, V=50, E=2000;
	printf("%d\n", V);
	for(i=0; i < V; ++i){
		printf("%d ", E);
		for(j=0; j < E; ++j) printf("1 1 ");
		puts("");
	}
	int Q = 10;
	printf("%d\n", Q);
	while(Q--){
		printf("%d %d\n", 0, V-1);
	}
}

pichulia 9년 전 1

문제에 나와있는 벨만포드 코드를 보시면 아래와 같은 부분이 있습니다.

change 변수가 변하지 않고 false를 유지한다면 강제로 알고리즘을 종료하는 부분이죠.

현재 1에서 1로 가는 간선만 우다다다 있는데, 이런 경우 dist[1]의 값이 변하지 않기 때문에

change = true; 부분이 실행되지 않을 것입니다.

그렇다고 가중치를 음수로 주면 문제 조건에 맞지 않으니...크크킄..;;

잘 해보세요 (...?!!!)

간선을 많이 배치하면 되는건 맞습니다.

      change = false;
      for (u = 0; u < V; u++)
        for (j = 0; j < (int)AdjList[u].size(); j++) {
          counter++;
          if (counter > 1000000) {
            printf("TLE because iteration counter > 1000000\n");
            return 1;
          }

          IntPair v = AdjList[u][j];
          
          if (dist[u] + v.second < dist[v.first]) {
            dist[v.first] = dist[u] + v.second;
            change = true;
          }
        }

      if (!change) // the optimized BellmanFord
        break;

joonas 9년 전 0

감사합니다. 최대 T=2222를 넘기면 안되는 거군요 ㅠ

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

문제

문제

출처

ICPC

7141번 T 질문

joonas 9년 전 0

pichulia 9년 전 0

joonas 9년 전 1

joonas 9년 전 0

pichulia 9년 전 1

joonas 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말