oj.uz

답안 #409203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409203 2021-05-20T10:58:12 Z Nodir_Bobiev 통행료 (APIO13_toll) C++17
0 / 100
 1 ms 204 KB 
# include <bits/stdc++.h>
using namespace std;

int n, m, k, A, B, p[15];
vector < vector < int > > graph[15];

int mstWeight;
vector < vector < int > > mstEdges;

void PrimaAlgo(int weight = 0){
    mstWeight = 0;
    mstEdges.clear();
    priority_queue < vector < int > > pq;

    int used[n+1] = {};
    if( weight == 0 ){
        used[1] = 1;
        for( auto c: graph[1] )
            pq.push({-c[0], 1, c[1]});
    }else{
        mstWeight = weight;
        used[A] = used[B] = 1;
        for( auto c: graph[A] )
            pq.push({-c[0], A, c[1]});
        for( auto c: graph[B] )
            pq.push({-c[0], B, c[1]});
    }

    for( int turn = 2; turn <= n; turn ++ ){
        vector < int > edge;
        while( !pq.empty() ){
            edge = pq.top(); pq.pop();
            if( used[edge[2]] == false )
                break;
        }
        int v = edge[2];
        if( used[v] )
            break;

        edge[0] = -edge[0];
        mstWeight += edge[0];
        mstEdges.push_back(edge);

        used[v] = true;
        for( auto c: graph[v] )
            pq.push({-c[0], v, c[1]});
    }
}

vector < int > simpleGraph[15];
bool vis[15];

void dfs( int v ){
    vis[v] = true;
    for( auto to: simpleGraph[v] )
        if( !vis[to] )
            dfs(to);
}

int main(){
    cin >> n >> m >> k;
    vector < int > weights;
    for( int i = 0; i < m; i ++ ){
        int a, b, c;
        cin >> a >> b >> c;
        weights.push_back(c);
        graph[a].push_back({c, b});
        graph[b].push_back({c, a});
    }
    cin >> A >> B;
    for( int i = 1; i <= n; i ++ )
        cin >> p[i];

    PrimaAlgo();
    int minMstWeight = mstWeight;
    int ans = 0; // = inf;

    for( auto weight: weights ){
        PrimaAlgo(weight);
        if( minMstWeight >= mstWeight ){
            for( int i = 1; i <= n; i ++ ){
                simpleGraph[i].clear();
                vis[i] = 0;
            }
            for( auto edge: mstEdges ){
                simpleGraph[edge[1]].push_back(edge[2]);
                simpleGraph[edge[2]].push_back(edge[1]);
            }
            dfs(1);
            int totalP = 0;
            for( int i = 1; i <= n; i ++ ){
                if( !vis[i] )
                    totalP += p[i];
            }
            ans = max( ans, totalP * weight );
        }
    }
    cout << ans;
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -