본문 바로가기

Programming Problems

네트워크 증폭 최소화 문제 ( 다익스트라 최소경로 곱셈 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
double findmin(vector<vector<pair<intdouble>>> & graph) {
    vector<double> dist(graph.size(), 999999999);
    priority_queue<pair<doubleint>vector<pair<doubleint>>, greater<pair<doubleint>>> q;
    dist[0= 1;
    q.push(pair<doubleint>(10));
    while (q.size() != 0) {
        int curr = q.top().second;
        double currd = q.top().first;
        q.pop();
        if (currd > dist[curr]) continue;
        // check adjacent elements
        for (int i = 0; i < graph[curr].size(); i++) {
            int n = graph[curr][i].first;
            double nd = graph[curr][i].second;
            if (dist[n] > currd*nd) {
                dist[n] = currd * nd;
                q.push(pair<doubleint>(dist[n], n));
            }
        }
    }
    return dist[graph.size() - 1];
}
cs