Algorithm 문제

[백준] 1238 - 파티

노예2 2019. 6. 28. 18:03

https://www.acmicpc.net/problem/1238

 

1238번: 파티

문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때

www.acmicpc.net

 

간단한 플로이드-워셜 알고리즘 문제

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다.[1][2] 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R

ko.wikipedia.org

3중첩 for-loop를 이용하여 최단 경로를 제공하는 경유지를 탐색한다.

 

<C++ 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <algorithm>
using namespace std;
 
int dist[1001][1001];
 
int main(){
    int n, m, x;
    scanf("%d %d %d", &n, &m, &x);
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            dist[i][j] = 1000000;
        }
        dist[i][i] = 0;
    }
 
    for(int i=0; i<m; i++){
        int s, e, v;
        scanf("%d %d %d", &s, &e, &v);
        dist[s][e] = min(dist[s][e], v);
    }
 
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
 
    int re = 0;
    for(int i=1; i<=n; i++){
        re = max(re, dist[i][x] + dist[x][i]);
    }
    printf("%d", re);
 
    return 0;
}
cs