oj.uz

답안 #409218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409218 2021-05-20T11:25:26 Z Nodir_Bobiev 통행료 (APIO13_toll) C++17
16 / 100
 228 ms 332 KB 
# include <bits/stdc++.h>
using namespace std;

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

bool vis[15];
void dfs( int v ){
    vis[v] = true;
    for( auto to: graph[v] ){
        if( vis[to[0]] == false )
            dfs(to[0]);
    }
}

void constructGraph(int i){
     for( int j = 1; j <= n; j ++ ){
            graph[j].clear();
            vis[j] = false;
        }

    for( int j = 0; j < m; j ++ )
        if( ((i>>j)&1) ){
            graph[edges[j][0]].push_back({edges[j][1], edges[j][2]});
            graph[edges[j][1]].push_back({edges[j][0], edges[j][2]});
        }
}
bool isTree(){
    bool isConnected = true;
    for( int j = 1; j <= n; j ++ )
        if( vis[j] == false )
            isConnected = false;
    return isConnected;
}
int DFS( int v, int f ){
    int res = p[v];
    for( auto to: graph[v] ){
        if( to[0] == f )
            continue;
        int x = DFS(to[0], v);
        res += x;
        if( (v == A && to[0] == B) || (v == B && to[0] == A) )
            totalP = x;
    }
    return res;
}
int main(){
    cin >> n >> m >> k;
    for( int i = 0; i < m; i ++ ){
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back({a,b,c});
    }
    cin >> A >> B;
    for( int i = 1; i <= n; i ++ )
        cin >> p[i];

    int minWeight = 1e9; // 1e9 = 10^9;  1e6 = 1o^6;
    int mst;

    for( int i = 0; i < (1<<m); i ++ ){
        if( __builtin_popcount(i) != n-1 )
            continue;

        constructGraph(i);

        dfs(1);


        if( isTree() == false )
            continue;

        int totalWeight = 0;
        for( int j = 0; j < m; j ++ )
            if( ((i >> j) & 1) )
                totalWeight += edges[j][2];

        if( totalWeight < minWeight ){
            minWeight = totalWeight;
            mst = i;
        }
    }
    constructGraph(mst);
    int maxWeight = 0, P = 0;
    for( int j = 0; j < m; j ++ ){
        if( ((mst >> j) & 1) ){
            mst -= (1<<j);
            constructGraph(mst);
            graph[A].push_back({B, 0});
            graph[B].push_back({A, 0});
            dfs(1);
            if( isTree() ){
                DFS(1, -1);
                if( edges[j][2] > maxWeight ){
                    maxWeight = edges[j][2];
                    P = totalP;
                }
            }
            mst += (1<<j);
        }
    }
    cout << 1ll*maxWeight * P;
}
/*
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
*/

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:88:17: warning: 'mst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |             mst -= (1<<j);
      |             ~~~~^~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 268 KB Output is correct
2 Correct 118 ms 268 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 268 KB Output is correct
2 Correct 118 ms 268 KB Output is correct
3 Runtime error 4 ms 332 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 268 KB Output is correct
2 Correct 118 ms 268 KB Output is correct
3 Runtime error 4 ms 332 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 268 KB Output is correct
2 Correct 118 ms 268 KB Output is correct
3 Runtime error 4 ms 332 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 268 KB Output is correct
2 Correct 118 ms 268 KB Output is correct
3 Runtime error 4 ms 332 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -