Submission #409213

#	Time	Username	Problem	Language	Result	Execution time	Memory
409213		Nodir_Bobiev	Toll (APIO13_toll)	C++17	16 / 100	1 ms	296 KiB

toll

# 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] = true;
        for( auto c: graph[1] )
            pq.push({-c[0], 1, c[1]});
    }else{
        mstWeight = weight;
        used[A] = used[B] = true;
        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;
    long long ans = 0;

    for( auto weight: weights ){
        PrimaAlgo(weight);
        if( minMstWeight >= mstWeight ){
            for( int i = 1; i <= n; i ++ ){
                simpleGraph[i].clear();
                vis[i] = false;
            }
            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 * 1ll * 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: 16 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22