cow party

문제

N 개 농장의 (편의상 1 ,2 .. , N) 의 대표 암소 한 마리가, X ( 1 <= X <= N) 농장에서 열리는 파티에 참석하려고 한다. 농장들은 단방향의 길들로 연결되어 있으며, 각 길마다 걸어가는데 걸리는 시간이 주어진다.

모든 소들은 파티에 걸어가야 하고 파티가 마친 후에는 자기가 속한 농장으로 돌아와야 한다. 모든 소들은 게을러서 가장 최단시간으로 올수 있는 최적의 길을 선택하려고 한다.

모든 소 들 중에서 농장으로 갔다가 돌아오는 데 가장 많이 걸리는 소의 시간은 얼마인가?

시간제한 : 0.5 초

---

입력

첫 번째 줄 : 정수 N , M , X 가 주어진다. (1<=N<=1000)는 농장의 수, (1<=M<=N*(N-1))은 도로의 갯수, (1<=X<=N)는 파티가 열리는 농장이다.

두 번재 줄에서 M+1 번째 줄 : i+1 번째 줄은 세 정수 Ai,Bi,Ci 가 주어진다. Ai 에서 Bi 로 가는데 Ti 시간이 소요된다는 것이다.

---

출력

파티에 참석했다 돌아오는 소 들 중 가장 긴 시간을 출력한다.

---

힌트

입력 예제

4 8 2

1 2 4

1 3 2

1 4 7

2 1 1

2 3 5

3 1 2

3 4 4

4 2 3

출력 예제

10

4 -> 2 ( 3 )

2 -> 1 -> 3 -> 4 (7)

총 거리합은 10이고, 이 때가 가장 긴 경우이다.

#include <iostream> #include <fstream> #include <vector> #include <queue> #include <limits.h> using namespace std; //농장, 길, 도착지 int N, M, X; // 1<=N<=1000 // 1<=M<=N * (N-1) // 1<=X<=N struct Node { int a; int b; int c; }; vector<Node> pathV[1001]; int BFS(int start, int end) { queue<int> tripQ; tripQ.push(start); int C[1001]; for (int i = 1; i <= N; i++) { C[i] = INT_MAX; } C[start] = 0; while (!tripQ.empty()) { int num = tripQ.front(); tripQ.pop(); vector<Node>::iterator iter; for (iter = pathV[num].begin(); iter != pathV[num].end(); iter++) { Node n = *iter; if (C[n.a] + n.c < C[n.b]) { C[n.b] = C[n.a] + n.c; tripQ.push(n.b); } } } return C[end]; } int main() { cin >> N >> M >> X; int a, b, c; for (int i = 1; i <= M; i++) { cin >> a >> b >> c; pathV[a].push_back({ a,b,c }); } int MAX = 0; for (int i = 1; i <= N; i++) { int res1 = BFS(i,X); int res2 = BFS(X,i); if (res1+res2 > MAX) { MAX = res1 + res2; } } cout << MAX << endl; return 0; }