#include <stdio.h> #include <iostream> #include <vector> #include <queue> using namespace std; int graph[1010][1010]; int V, E, arrive; int Max; void floyd() { for(int k = 1; k <= V; k++) { for(int i = 1; i <= V; i++) { for(int j = 1; j <= V; j++) { if(graph[i][k] + graph[k][j] < graph[i][j]) { graph[i][j] = graph[i][k] + graph[k][j]; } } } } } int main(void) { // freopen("B1238_input.txt", "r", stdin); cin >> V >> E >> arrive; for(int i = 1; i <= V; i++) { for(int j = 1; j <= V; j++) { if(i == j) { graph[i][j] = 0; } else { graph[i][j] = 99999999; } } } for(int i = 1; i <= E; i++) { int from, to, weight; cin >> from >> to >> weight; graph[from][to] = weight; } floyd(); for(int i = 1; i <= V; i++) { if(Max < graph[i][arrive] + graph[arrive][i]) { Max = graph[i][arrive] + graph[arrive][i]; } } cout << Max; return 0; } | cs |
'Baekjoon > Graph' 카테고리의 다른 글
[백준 16681] 등산 (Dijkstra) (C/C++) (★★) (0) | 2020.02.18 |
---|---|
[백준 2211] 네트워크 복구 (Dijkstra) (C/C++) (0) | 2020.02.18 |
[백준 1238] 파티 (Floyd-Warshall) (C/C++) (0) | 2020.02.17 |
[백준 1916] 최소비용 구하기 (Dijkstra) (C/C++) (0) | 2020.02.16 |
[백준 1753] 최단경로 (Dijkstra) (C/C++) (0) | 2020.02.16 |