Submission #1034820
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) #define all(c) (c).begin(), (c).end() #define zero(a) memset(a, 0, sizeof a) #define minus(a) memset(a, -1, sizeof a) #define watch(a) { cout << #a << " = " << a << endl; } template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); } template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); } template<class T> void operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) cin >> e; } typedef long long ll; int const inf = 1<<29; namespace tree { struct union_find { vector<int> par, rank, size; int compnum; union_find(int N) { compnum = N; par.resize(N), rank.resize(N), size.resize(N); for(int i=0; i<N; i++) { par[i] = i; rank[i] = 0; size[i] = 1; } } int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); } void unite(int x, int y) { x = root(x), y = root(y); if(x == y) return; if(rank[x] < rank[y]) { par[x] = y, size[y] += size[x]; } else { par[y] = x, size[x] += size[y]; if(rank[x] == rank[y]) rank[x]++; } compnum--; } int operator[](int x) { return root(x); } void operator()(int x, int y) { return unite(x, y); } bool same(int x, int y) { return root(x) == root(y); } int size_of(int x) { return size[root(x)]; } int num_of_comps() { return compnum; } }; } int dist[4000][4000]; vector<pair<int, int>> G[4000]; tuple<int, int, int> es[4000]; void dfs(int curr, int par, int start, int max) { dist[curr][start] = max; for(auto const& e: G[curr]) { if(e.first != par) dfs(e.first, curr, start, std::max(max, e.second)); } }; int main() { int N, M; cin >> N >> M; rep(i, M) { int a, b, c; scanf("%d%d%d", &a, &b, &c); a--, b--; es[i] = {c, a, b}; G[a].push_back({b, c}); G[b].push_back({a, c}); } sort(es, es+N); tree::union_find uf(N); ll rawMSTWeight = 0; rep(i, M) { int a, b, c; tie(c, a, b) = es[i]; if(!uf.same(a, b)) { uf.unite(a, b); rawMSTWeight += c; } } rep(i, N) { dfs(i, -1, i, 0); } int Q; cin >> Q; rep(i, Q) { int s, t; scanf("%d%d", &s, &t); s--, t--; cout << rawMSTWeight - dist[s][t] << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | motxx |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2467 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:76:11: error: converting to ‘std::tuple<int, int, int>’ from initializer list would use explicit constructor ‘constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {int&, int&, int&}; <template-parameter-2-2> = void; _Elements = {int, int, int}]’ es[i] = {c, a, b}; ^ ./Main.cpp:74:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int a, b, c; scanf("%d%d%d", &a, &b, &c); ^ ./Main.cpp:101:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int s, t; scanf("%d%d", &s, &t); s--, t--; ^