[백준] 1238번: 파티 / C++

✏️ 문제 링크

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

1238번: 파티

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

1. i번째 학생이 X마을에 도착하는 최단 시간을 구한다.

2. X마을에서 i번째 마을로 i번째 학생이 돌아오는 최단 시간을 구한다. 

3. 1,2번의 결과 값을 더해 answer에 max값을 넣어준다. 

 for(int i=1; i<=N; i++){
        //각 i번째 학생이 X 마을에 도착하는시간
        int ItoX=dijkstra(i, X);
        //i번째 학생이 X마을에서 출발해 돌아오는 시간
        int XtoI=dijkstra(X, i);
        answer=max(answer, ItoX+XtoI);
}

 

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
using pii=pair<int, int>;

#define MAX 1001
#define INF 987654321

vector<pii> vec[MAX];
int N, M, X;
int dijkstra(int s, int e){
   vector<int> dist(N+1, INF);
   priority_queue<pii> pq; pq.push({0, s});
   dist[s]=0;
   while(!pq.empty()){
       pii t=pq.top(); pq.pop();
       int c=t.second; int d=t.first*-1;
       
       if(dist[c]<d)continue;
       
       for(int i=0; i<vec[c].size(); i++){
           int nxt=vec[c][i].first;
           int nxt_d=vec[c][i].second + d;
           if(dist[nxt]>nxt_d){
               dist[nxt]=nxt_d;
               pq.push({nxt_d*-1, nxt});
           }
       }
   }

   return dist[e]; 
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int answer=0; cin>>N>>M>>X;
    
    while(M--){
        int a, b, c; cin>>a>>b>>c;
        vec[a].push_back({b, c});
    }
    
    for(int i=1; i<=N; i++){
        //각 i번째 학생이 X 마을에 도착하는시간
        int ItoX=dijkstra(i, X);
        //i번째 학생이 X마을에서 출발해 돌아오는 시간
        int XtoI=dijkstra(X, i);
        answer=max(answer, ItoX+XtoI);
    }
    
    cout<<answer<<"\n";
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐