Submission #22588

#	Time	Username	Problem	Language	Result	Execution time	Memory
22588		카시코이 (#40)	Logistical Metropolis (KRIII5_LM)	C++11	2 / 7	86 ms	1356 KiB

LM

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;

struct edge{
  int x, y, d;
  bool operator< (const edge& rhs) const {
    return d < rhs.d;
  }
};

vector<edge> e;
vector<pair<int, int> > con[1010];
int par[1010];

int getpar(int x){
  if(x == par[x]) return x;
  return (par[x] = getpar(par[x]));
}

int main(){
  int N, M; scanf("%d%d", &N, &M);
  assert(N <= 1000);

  for(int i = 0; i < M; i++){
    int x, y, d; scanf("%d%d%d", &x, &y, &d);
    con[x].push_back({y, d});
    con[y].push_back({x, d});
    e.push_back({x, y, d});
  }

  sort(e.begin(), e.end());

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

    int s = 0;
    for(auto &pp : con[V]){
      s += pp.second; par[pp.first] = V;
    }

    for(edge& ee : e){
      int px = getpar(ee.x);
      int py = getpar(ee.y);

      if(px != py){
        s += ee.d; par[py] = px;
      }
    }

    printf("%d\n", s);
  }
  return 0;
}

Compilation message (stderr)

LM.cpp: In function 'int main()':
LM.cpp:24:34: 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:28:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int x, y, d; scanf("%d%d%d", &x, &y, &d);
                                             ^

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