백준 문제 1238번 파티 문제풀이 c++

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

1238번: 파티

 

문제해석

 

예를 들어 n=4 ,x=2 인 경우를 생각해보자

1->2 + 2->1

2->2 + 2->2 (시작점 끝점이 같은경우는 없음)

3->2 + 2->3

4->2 + 4->1 이 세가지 경우 중에 가장 작은 값이 답이 된다.

따라서 각 마을에서 마을까지 전부 다익스트라를 돌리든 플로이드를 돌리든 최단 거리를 저장시켜놔야한다고 생각했다.

 

마을개수가 최대 1000이므로 플로이드를 사용하여 구현하면 1000*1000*1000=10억 이므로 시간 초과가 날것 같아서 그렇게 하는건 포기했고 전부 다익스트라를 돌려서 풀어보기로 했다.

 

전부 다익스트라를 돌려볼거니까 d배열을 2차원으로 수정하고 그 외 자잘한 부분을 수정한거 빼고 저번에 작성한 다익스트라 코드를 거의 그대로 사용하였다.

 

전부 다익스트라를 돌린 후에 d[i][j]는 i마을에서 j마을까지 최단거리가 저장되어있을것이다.

그 중 x마을로 갔다가 돌아오는 거리가 가장 짧은 것을 답으로 출력하면 끝

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
#define INF 999999999
using namespace std;
int getsmall();
void dijk(int start);
void reset();
priority_queue < pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > >pq;
vector < pair<int,int> > v[1001];
int d[1001][1001];
bool visited[1001];
int n,m,x;
int main(){
	cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n>>m>>x;
    for(int i=0; i<m; i++)
    {
        int s,e,t;
        cin>>s>>e>>t;
        v[s].push_back({t,e});
    }
    for(int i=1; i<=n; i++)
    {
        reset();
        dijk(i);
    }
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        ans=max(d[i][x]+d[x][i],ans);
    }
    cout<<ans;
}
void dijk(int start){
    for(int i=1; i<=n; i++)
    {
        d[start][i]=INF;
    }
    d[start][start]=0;
    for(int i=0; i<v[start].size(); i++)
    {
        d[start][v[start][i].second]=v[start][i].first;
        pq.push({v[start][i].first,v[start][i].second});
    }
    visited[start]=1;
    for(int j=0; j<n; j++)
    {
        int cur=getsmall();
        visited[cur]=1;
        for(int i=0; i<v[cur].size(); i++)
        {
            if(visited[v[cur][i].second]==0&&d[start][cur]+v[cur][i].first<d[start][v[cur][i].second])
            {
                d[start][v[cur][i].second]=d[start][cur]+v[cur][i].first;
                pq.push({d[start][v[cur][i].second],v[cur][i].second});
            }
        }
    }
}
int getsmall(){
    int index=0;
    while(!pq.empty())
    {
        index=pq.top().second;
        pq.pop();
        if(visited[index]==0)
        {
            return index;
        }
    }
    return index;
}
void reset(){
    pq=priority_queue < pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > >();
    memset(visited,0,sizeof(visited));
}