Twinparadox Factory

시간 제한 : 1초메모리 제한 : 128MB 입력첫째 줄에 N(1 m >> x; for (int i = 0; i > v1 >> v2 >> w; if(graph[v1-1][v2-1] > w) graph[v1 - 1][v2 - 1] = w; } Floyd(); max = -1; for (int i = 0; i < n; i++) { weight = graph[i][x - 1] + graph[x - 1][i]; max = max < weight ? weight : max; } cout

시간 제한 : 1초메모리 제한 : 128MB 입력첫째 줄에 학생들의 수 N (2 m; for (int i = 0; i > v1 >> v2; graph[v1 - 1][v2 - 1] = 1; } Floyd(); ans = 0; for (int i = 0; i < n; i++) { cnt = 0; for (int j = 0; j < n; j++) if (i != j) cnt += (graph[i][j] + graph[j][i]); if (cnt == n - 1) ans++; } cout

모든 쌍의 최단 경로를 구하는 방법을 찾고 싶다면, 다익스트라(Dijkstra) 알고리즘을 모든 정점(Vertex)에 대한 최단경로를 구하거나 다익스트라가 제한되는 경우(음의 가중치가 존재하는 경우)에는 벨만-포드(Bellman-Ford) 알고리즘을 모든 정점(Vertex)에 대해서 사용하면 된다. 플로이드-워셜(Floyd-Warshall) 알고리즘은 앞서 말한 두 알고리즘과는 다르게 처음부터 모든 정점 사이의 최단 경로를 구하는 알고리즘이다. 위 그림은 i에서 j로 가는 방법을 표현한 것으로, k를 경유하는 경우와 그렇지 않은 경우에 대한 것이다. 위 문자의 의미는 1부터 k까지만 경유할 수 있는 상황에서 i에서 j까지 갈 수 있는 모든 경로 중, 가장 짧은 경로의 거리로, 동적계획법(Dynamic P..

시간 제한 : 1초메모리 제한 : 256MB 입력첫째 줄에 도시의 개수 n(1≤n≤100)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 출력N개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다. 소스코드 #include #define ..