Submission #22647

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22647	2017-04-30T06:07:00 Z	나자바봐랑(#989, SCIK, devetude)	Logistical Metropolis (KRIII5_LM)	C++	0 / 7	2000 ms	7088 KB

LM

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

class Node {
public:
    int idx;
    int cost;
    
public:
    Node(int idx, int cost) {
        this->idx = idx;
        this->cost = cost;
    }
};

class Bridge {
public:
    int from;
    int to;
    int cost;
    
public:
    Bridge(int from, int to, int cost) {
        this->from = from;
        this->to = to;
        this->cost = cost;
    }
    
    bool operator<(const Bridge& b) const {
        return cost < b.cost ? false : true;
    }
};

int find(int* parents, int k) {
    if (parents[k] == k) {
        return k;
    }
    
    return parents[k] = find(parents, parents[k]);
}

bool combine(int* parents, int a, int b) {
    int aParents = find(parents, a);
    int bParents = find(parents, b);
    
    if (aParents != bParents) {
        parents[bParents] = aParents;
        
        return true;
    }
    
    return false;
}

int main(void) {
    int N, M;
    scanf("%d %d", &N, &M);
    
    vector<Node> list[N + 1];
    
    for(int i = 1; i <= N; i++) {
        int start, end, cost;
        scanf("%d %d %d", &start, &end, &cost);
        
        list[start].push_back(Node(end, cost));
        list[end].push_back(Node(start, cost));
    }
    
    for (int major = 1; major <= N; major++) {
        int parents[N + 1];
        
        for (int i = 1; i <= N; i++) {
            parents[i] = i;
        }
        
        int totalCost = 0;
        
        for (Node n : list[major]) {
            totalCost += n.cost;
            parents[major] = n.idx;
        }
        
        priority_queue<Bridge> priorityQueue;
        
        for (int start = 1; start <= N; start++) {
            if (start != major) {
                for (Node n : list[start]) {
                    if (n.idx != major) {
                        priorityQueue.push(Bridge(start, n.idx, n.cost));
                    }
                }
            }
        }
        
        unsigned long V = N - list[major].size();
        
        while (V > 1) {
            Bridge bridge = priorityQueue.top();
            priorityQueue.pop();
            
            if (combine(parents, bridge.from, bridge.to)) {
                totalCost += bridge.cost;
                V--;
            }
        }
        
        printf("%d\n", totalCost);
    }
    
    return 0;
}

Compilation message

LM.cpp: In function 'int main()':
LM.cpp:81:23: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
         for (Node n : list[major]) {
                       ^
LM.cpp:90:31: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
                 for (Node n : list[start]) {
                               ^
LM.cpp:60:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
                           ^
LM.cpp:66:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &start, &end, &cost);
                                               ^

Subtask #1

0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2000 ms	1172 KB	Execution timed out
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2000 ms	7088 KB	Execution timed out
2	Halted	0 ms	0 KB	-