글 읽기 - 1238 c++ 개념 질문 드립니다.

hena_42 2년 전 0

안녕하세요 C++ 연습하는 코린이 입니다.

14번 째 줄void dijkstra(vector graph[], int start, vector &d)이 함수에 대해 궁금한게 생겨서 질문드립니다.

처음 제출 하였던 방식은 위의 방식처럼 제출하였습니다. c++에는 참조자라는 것이 존재한다고 하여서, 복사하는 것보다는 참조값을 사용하여 복사를 방지하려고 하였습니다.

void dijkstra(vector (&graph)[], int start, vector &d); 이렇게 못 쓰는 이유와 처음에 보여드린 방식과 메모리 사용량과 실행 시간이 같은 이유가 알고싶습니다.

#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
int n, m, x;
struct Data{
    int v;
    int w;
    bool operator<(const struct Data &copy) const
    {
        return w > copy.w;
    }
};

void dijkstra(vector<Data> (&graph)[1001], int start, vector<int> &d)
{
    d[start] = 0;
    
    priority_queue<Data> pq;
    pq.push({start, 0});
    while (!pq.empty())
    {
        int now = pq.top().v;
        int nowCost = pq.top().w;
        pq.pop();
        if (d[now] < nowCost)
            continue;
        for (int i = 0 ; i < graph[now].size() ; ++i)
        {
            int next = graph[now][i].v;
            int nextCost = graph[now][i].w + d[now];
            if (nextCost < d[next])
            {
                d[next] = nextCost;
                pq.push({next, nextCost});
            }
        }
    }
}

int main()
{
    vector<Data> come[1001];
    vector<Data> back[1001];
    vector<int> dist_come(1001, INF);
    vector<int> dist_back(1001, INF);
    cin >> n >> m >> x;
    int v1, v2, w;
    for (int i = 0 ; i < m ; ++i){
        cin >> v1 >> v2 >> w;
        come[v1].push_back({v2, w});
        back[v2].push_back({v1, w});
    }
    for (int i = 1 ; i<= n ; ++i)
    {
        dist_come[i] = INF;
        dist_back[i] = INF;
    }
    dijkstra(come, x, dist_come);
    dijkstra(back, x, dist_back);
    int maxValue = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        // cout << dist_come[i] << ' ' << dist_back[i] << '\n';
        int total = dist_come[i] + dist_back[i];
        if (total <= INF && total > maxValue)
            maxValue = total;
    }
    cout << maxValue;
}

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

문제

문제

출처

ICPC

1238 c++ 개념 질문 드립니다.

hena_42 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말