1238_파티

Concept & Idea

이 문제에서 가장 중요한 아이디어는 다익스트라를 두번 사용해야 한다는 점이다.
어떤 지점에서 X까지 도달하는 최소 거리 + X에서 어떤 지점까지 도달하는 최소 거리의 합의 최댓값을 구하는 문제였다.
필자는 시간초과 문제를 마주하여,, 몇 시간동안 고민했지만 바보같은 사고를 하였다.
X에서 어떤 지점까지 가는 최솟값은 두번째 다익스트라로 해결하였다.
어떤 지점에서 X까지 가는 것은 N번 돌렸었는데, X의 지점을 최대한 이용하여, 역방향 거리를 가지고 있는 벡터를 만들어서 그 벡터를 X에서 출발하면 해결할 수 있는 문제였다.

해당 테스트 케이스에서
DP1에는 4,0,6,3
DP2에는 1,0,3,7 이 들어있어서 정답 10을 구할 수 있다.

Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node{
    int x,y,z;
    bool operator()(node a, node b){
        return a.z>b.z;
    }
};
vector<pair<int, int>> vec[1002];
vector<pair<int, int>> vec2[1002];
priority_queue<node, vector<node>, node> pqu;
int dp[1][1002],dp2[1][1002];
int main(){
    int n,m,x;
    scanf("%d %d %d", &n, &m, &x);
    for(int i=0; i<m; i++) {
        int a,b,c;
        scanf("%d %d %d", &a, &b, &c);
        vec[a].push_back({b,c});
        vec2[b].push_back({a,c});
    }
    int res=-1;
    for(int j=1; j<=n; j++) {
        dp[0][j]=100000001;
    }
    dp[0][x]=0;
    for(int j=0; j<vec2[x].size(); j++) {
        node t;
        t.x = x; t.y=vec2[x][j].first; t.z=vec2[x][j].second;
        pqu.push(t);
    }
    while(!pqu.empty()) {
        node temp = pqu.top();
        pqu.pop();
        if(dp[0][temp.y]>dp[0][temp.x]+temp.z) {
            dp[0][temp.y]=dp[0][temp.x]+temp.z;
            for(int j=0; j<vec2[temp.y].size(); j++) {
                node t;
                t.x = temp.y; t.y=vec2[temp.y][j].first; t.z=vec2[temp.y][j].second;
                pqu.push(t);
            }
        }
    }
    for(int j=1; j<=n; j++) {
        dp2[0][j]=100000001;
    }
    dp2[0][x]=0;
    for(int j=0; j<vec[x].size(); j++) {
        node t;
        t.x = x; t.y=vec[x][j].first; t.z=vec[x][j].second;
        pqu.push(t);
    }
    while(!pqu.empty()) {
        node temp = pqu.top();
        pqu.pop();
        if(dp2[0][temp.y]>dp2[0][temp.x]+temp.z) {
            dp2[0][temp.y]=dp2[0][temp.x]+temp.z;
            for(int j=0; j<vec[temp.y].size(); j++) {
                node t;
                t.x = temp.y; t.y=vec[temp.y][j].first; t.z=vec[temp.y][j].second;
                pqu.push(t);
            }
        }
    }
    for(int i=1; i<=n; i++) {
        res=max(res, dp[0][i]+dp2[0][i]);
    }
    cout<<res<<endl;
}

Fealing

다익스트라를 두 번 사용하면 된다는 생각은 잘했지만,, 한 가지 생각이 부족했다…
최소비용 만들기 문제에서는 n번 다익스트라를 돌려서 확인했기 때문에,, 이번에도 N번하면 된다고 생각했지만,, 그것이 아니었다.
그래도 다음번에는 이런 생각을 더 할 수 있지 않을까 싶다!