Submission #22764

#	Time	Username	Problem	Language	Result	Execution time	Memory
22764		dried chocochip on Daegu asphalt (#40)	Logistical Metropolis (KRIII5_LM)	C++98	2 / 7	103 ms	4852 KiB

LM

//
// Created by Acka on 2017. 4. 30..
//

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge{
    int u, v, c;
    Edge(){}
    Edge(int u, int v, int c):u(u), v(v), c(c){}
    bool operator <(const Edge &A)const{
        return c < A.c;
    }
};

int par[1001];
Edge edge[300000];
vector<Edge> adj[1001];

int find(int x){
    return x == par[x] ? x : par[x] = find(par[x]);
}

void link(int x, int y){
    par[find(y)] = find(x);
}

int main()
{
    int N, M; scanf("%d %d", &N, &M);
    for(int i = 0, x, y, c; i < M; i++){
        scanf("%d %d %d", &x, &y, &c);
        edge[i] = Edge(x, y, c);
        adj[x].push_back(Edge(0, y, c));
        adj[y].push_back(Edge(0, x, c));
    }

    sort(edge, edge + M);

    for(int o = 1; o <= N; o++){
        for(int i = 1; i <= N; i++)
            par[i] = i;

        int sum = 0;
        for(int i = 0; i < adj[o].size(); i++){
            link(o, adj[o][i].v);
            sum += adj[o][i].c;
        }

        for(int i = 0; i < M; i++){
            int pu = find(edge[i].u), pv = find(edge[i].v);
            if(pu == pv) continue;
            link(pu, pv);
            sum += edge[i].c;
        }

        printf("%d\n", sum);
    }

    return 0;
}

Compilation message (stderr)

LM.cpp: In function 'int main()':
LM.cpp:48:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < adj[o].size(); i++){
                          ^
LM.cpp:33:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N, M; scanf("%d %d", &N, &M);
                                     ^
LM.cpp:35:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &x, &y, &c);
                                      ^

• Subtask 1: 2 / 2
• Subtask 2: 0 / 5