글 읽기 - 맞추신분 힌트점여.. 제 코드 공개되어 있어요

lsc4719 3년 전 0

최단경로 다익스트라

위상정렬

디피

이렇게 세가지 이용해서 풀려했는데 시간초과 납니다 ㅠㅠ

혹시 다른 풀이가 있나여

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Edge
{
    int to;
    int cost;
    
    Edge(int to, int cost):to(to),cost(cost){}
};

struct Graph
{
    const long long INF = 1e15;

    vector<vector<Edge>> adj;
    vector<long long> dist_from_src;
    vector<long long> topological_order;
    vector<int> in_degrees;

    const vector<Edge> &edges_from(int from)
    {
        return adj[from];
    }
    
    void init(int num_of_vertices)
    {
        adj.resize(num_of_vertices, vector<Edge>());
    }

    void add_edge(int from, int to, int cost)
    {
        adj[from].push_back(Edge(to, cost));
    }

    void fill_dist_from_src(int src_node)
    {
        dist_from_src.resize(adj.size(), INF);

        priority_queue<pair<long long, int>> node_to_visit;

        node_to_visit.push(make_pair(0, src_node));

        while(!node_to_visit.empty())
        {
            long long dist_to_get_here = node_to_visit.top().first;
            int node = node_to_visit.top().second;
            node_to_visit.pop();

            if(dist_to_get_here < dist_from_src[node])
            {
                dist_from_src[node] = dist_to_get_here;
            }
            else
            {
                continue;
            }

            for(const Edge &e : adj[node])
            {
                if(dist_from_src[node] + e.cost < dist_from_src[e.to])
                {
                    node_to_visit.push(make_pair(dist_from_src[node] + e.cost, e.to));
                }
            }
        }
    }

    void fill_in_degrees()
    {
        in_degrees.resize(adj.size(), 0);
        for(int from=0;from<adj.size();from++)
        {
            for(const Edge &e : adj[from])
            {
                in_degrees[e.to] += 1;   
            }
        }
    }

    void fill_topological_order()
    {
        fill_in_degrees();

        queue<int> node_to_visit;

        for(int node=0;node<adj.size();node++)
        {
            if(in_degrees[node] == 0)
            {
                node_to_visit.push(node);
            }
        }

        while(!node_to_visit.empty())
        {
            int node = node_to_visit.front();
            node_to_visit.pop();

            topological_order.push_back(node);

            for(const Edge &e : adj[node])
            {
                in_degrees[e.to] -= 1;
                if(in_degrees[e.to] == 0)
                {
                    node_to_visit.push(e.to);
                }
            }
        }
    }

    void print()
    {
        for(int from=0;from<adj.size();from++)
        {
            for(const Edge &e : adj[from])
            {
                printf("%d->%d\n", from, e.to);
            }
        }
    }
};

struct Solution
{
    int num_of_vertices;
    int num_of_edges;
    Graph graph_in;
    Graph graph_out;

    bool input()
    {
        scanf("%d", &num_of_vertices);
        if(num_of_vertices == 0) return true;

        scanf("%d", &num_of_edges);

        graph_in.init(num_of_vertices);

        for(int i=0;i<num_of_edges;i++)
        {
            int from;
            int to;
            int cost;
            scanf("%d%d%d", &from, &to, &cost);
            from -= 1;
            to -= 1;
            graph_in.add_edge(from, to, cost);
            graph_in.add_edge(to, from, cost);
        }

        return false;
    }
    int solve()
    {
        //graph_in.print();

        const int src_node = 0;
        const int sink_node = 1;
        graph_in.fill_dist_from_src(sink_node);

        graph_out.init(num_of_vertices);
        for(int node=0;node<num_of_vertices;node++)
        {
            for(const Edge &e : graph_in.edges_from(node))
            {
                if(graph_in.dist_from_src[node] > graph_in.dist_from_src[e.to])
                {
                    graph_out.add_edge(node, e.to, e.cost);
                }
            }
        }

        graph_out.fill_topological_order();

        reverse(graph_out.topological_order.begin(), graph_out.topological_order.end());

        vector<int> dp(graph_out.adj.size(), 0);

        dp[sink_node] = 1;

        for(int node : graph_out.topological_order)
        {
            //printf("node %d\n", node);
            for(const Edge &e : graph_out.edges_from(node))
            {
                if(graph_in.dist_from_src[node] > graph_in.dist_from_src[e.to])
                {
                    dp[node] += dp[e.to];
                }
            }
        }

        //graph_out.print();

        return dp[src_node];
    }
};

int main()
{
    while(true)
    {
        Solution s;
    
        bool end_of_input = s.input();

        if(end_of_input) break;

        cout << s.solve() << endl;
    }
    return 0;  
}

adh0463 3년 전 0

다익 + 위상 정렬 + dp로 풀었습니다.

올린 소스 다 읽진 않았지만..

S = 0, T = 1 두고,

문제에서 요구하는건 A에서 B로 이동할 수 있는 조건은 dist[A][T] > dist[B][T] 입니다. 따라서 시작을 S로 다익을 돌려버리면 단일 시작점 최단 경로를 구하기 때문에 dist[A][T] 또는 dist[B][T]의 조건은 전혀 알 수 없습니다.

힌트는 반대입니다 반대

똑같은 문제로는 2176번: 합리적인 이동경로 (acmicpc.net) 가 있구요,

lsc4719 3년 전 0

답변 감사합니다.

말씀하신대로 Dijkstra 사용할 때 시작 위치를 T로 두고 시작해야하는 데 S로 두고 시작한 버그를 수정해봤습니다.

말씀하신 부분을 수정 하였는데, 시간초과는 계속됩니다..

아이디어 자체는 맞는 것 같으니, 나중에 다시 풀어봐야겠습니다.

lsc4719 3년 전 0

아마도 구현하는 데 버그가 있는 것 같습니다 ㅠㅠ

adh0463 3년 전 0

init에 있는 resize이전에 clear해보시겟어요??

lsc4719 3년 전 0

위에 있는게 수정된 코드입니다. clear는 사용하지 않았습니다. 여러번 구현해보았는데도 틀리는 걸 보면 제가 계속 빠뜨리고 있는 부분이 있는 것 같습니다.

lsc4719 3년 전 0

풀게 된다면 정말 좋을 것 같습니다.

lsc4719 3년 전 0

위상정렬 하기 전에 그래프 만드는 부분을 좀 이상하게 처리한 것 같은데.. 하.. 구현을 다시..

adh0463 2년 전 0

c++에서 priority_queue는 최대힙으로 구현되어 있습니다.

아래처럼 소스를 변경하면 시간초과가 아니라 틀렸습니다가 나오네요 !

node_to_visit.push(make_pair(dist_from_src[node] + e.cost, e.to));
->
node_to_visit.push(make_pair(-(dist_from_src[node] + e.cost), e.to));

lsc4719 2년 전 0

감사합니다.

감사의 표시로 커피 한잔 사겠습니다.

선물이 도착했습니다! 선물코드를 등록하여 선물을 받아보세요.

∙ 선물코드 : YBXVSJXCD5
∙ 선물명 : 아이스 카페아메리카노 Tall
∙ 코드등록 유효기간 : 2021.04.25
∙ 코드등록 방법 : 카카오톡 > 선물하기 > 선물함 > 선물코드 등록
∙ 등록 URL : http://kko.to/--H4FGwYM

맛있게 드십쇼.

adh0463 2년 전 0

ㅋㅋㅋㅋ 잘마실게요, 열공하세요~

lsc4719 2년 전 1

MAX HEAP을 MIN HEAP으로 바꾸고 AC 받았습니다. 편안..

#include <functional>

priority_queue<pair<long long, int>,     
    vector<pair<long long, int>>, 
    greater<pair<long long, int>>> node_to_visit;

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

맞추신분 힌트점여.. 제 코드 공개되어 있어요

lsc4719 3년 전 0

adh0463 3년 전 0

lsc4719 3년 전 0

lsc4719 3년 전 0

adh0463 3년 전 0

lsc4719 3년 전 0

lsc4719 3년 전 0

lsc4719 3년 전 0

adh0463 2년 전 0

lsc4719 2년 전 0

adh0463 2년 전 0

lsc4719 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말