나그네

1865번: 웜홀 문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 어느 시작점에서 다시 시작 지점으로 돌아올 때 시간이 되돌아갈 수 있는지 여부를 구하는 문제다. 벨만 포드 알고리즘을 사용해 풀 수 있다. 도로는 양방향이지만 웜홀은 단방향임을 주의해야 한다. 처음엔 dist[1] < 0 이면 YES를 출력하도록 했다. 그러나 2%틀을 받고 모든 정점에서 다 해보는 코드를 짰는데 90% 언저리에서 시간초과가 났다. 결국 벨..

11657번: 타임머신 문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 그래프에서 1번 정점으로부터 각 정점으로의 최단 거리를 구하는 문제다. 가중치가 음수도 가능하므로 기본적인 벨만-포드 알고리즘으로 풀 수 있는 문제. 만약 무한정 작아질 수 있는 루프가 있으면 -1을 출력하면 된다. 코드 #include using namespace std; #define INF 1e18..