[백준 1238] 파티

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

1238번: 파티

요구사항

왕복이 가장 오래 걸리는 학생 찾기

 

풀이

다익스트라 알고리즘을 2번 써줘서

집-> 파티장 최단거리

파티장 -> 집 최단거리

를 구해서 가장 오래 걸리는 학생을 찾아준다

 

#include <stdio.h>

#include <iostream>
#include <queue>
#include <functional>
#include <vector>
#include <string.h>

using namespace std;

int n,m,k;
int dist[1001];
int dist1[1001];
struct go{
    int x;
    int y;
};
vector<go> v[20001];
int main()
{
    cin>>n>>m>>k;
    int ans=0;
    for(int i=0 ; i < m ; i++){
        int x, y,z;
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back({y,z});
    }
    
    for(int i=1; i<=n ; i++){
        for(int i=1;i<=n;i++){
            dist[i]=987654321;
            dist1[i]=987654321;
        }
        dist[i]=0;
        dist1[k]=0;
        priority_queue<pair<int,int>> q;
        priority_queue<pair<int,int>> q1;
        q.push({0,i});
        q1.push({0,k});
        while(!q.empty())
        {
         int now = q.top().second;
         int nowdist= -q.top().first;
         q.pop();
         for(int i=0 ; i < v[now].size();i++){
            int next = v[now][i].x;
            int d = nowdist +v[now][i].y;
         //   cout<<"d"<<d<<endl;
            if( dist[next] > d){
      //          cout<<"A"<<endl;
                dist[next]=d;
                q.push({-dist[next],next});
            }
         }
        
        }

        while(!q1.empty())
        {
          int now = q1.top().second;
            int nowdist= -q1.top().first;
            q1.pop();
            for(int i=0 ; i < v[now].size();i++){
                int next = v[now][i].x;
                int d = nowdist +v[now][i].y;
                if( dist1[next] > d){
                 dist1[next]=d;
                 q1.push({-dist1[next],next});
                }
            }
        }
        int tdist=dist[k]+dist1[i];
        if(tdist>ans)
            ans=tdist;

    //    cout<<"k"<<k<<"i"<<i<<endl;
    //    cout<<i<<" "<<dist[k]<< " " <<dist1[i]<< endl;

    }
    cout<<ans<<endl;
}