Submission #1628892
Source Code Expand
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;
int n, m, q;
int d[5010];
struct edge{
int to, cost;
// edge(int to, int cost):to(to), cost(cost){}
};
vector<edge> G[5010];
struct UF{
vector<int> par;
vector<int> sz;
UF(){}
UF(int n){
par.resize(n);
sz.resize(n, 1);
rep(i, 0, n) par[i] = i;
}
int find(int x){
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void unite(int x, int y){
x = find(x); y = find(y);
if(x == y) return;
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
par[y] = x;
}
bool same(int x, int y){
return find(x) == find(y);
}
};
vector<pair<int, P> > es;
vector<int> path;
int pMAX[4010][4010];
int cost[4010][4010];
void dfs(int now, int pre, int MAX, int root){
// cout << " " << now << " " << pre << endl;
path[now] = pre;
pMAX[root][now] = MAX;
// if(now == dest) return;
rep(i, 0, G[now].size()){
int next = G[now][i].to;
if(next == pre) continue;
// path[next] = now;
dfs(next, now, max(MAX, cost[now][next]), root);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
rep(i, 0, m){
int a, b, c;
cin >> a >> b >> c;
a--; b--;
// G[a].push_back(edge{b, c});
// G[b].push_back(edge{a, c});
es.push_back(pair<int, P>(c, P(a, b)));
cost[a][b] = c;
cost[b][a] = c;
}
sort(all(es));
UF uf(n);
int sum = 0, cnt = 0;
rep(i, 0, es.size()){
int from = es[i].second.first;
int to = es[i].second.second;
if(uf.same(from, to) == false){
uf.unite(from, to);
sum += es[i].first;
G[from]. push_back(edge{to, es[i].first});
G[to]. push_back(edge{from, es[i].first});
}
}
// cout << sum << endl;
rep(i, 0, n){
path.clear(); path.resize(n, -1);
dfs(i, -1, 0, i);
}
cin >> q;
rep(i, 0, q){
int s, t;
cin >> s >> t;
s--; t--;
// path.clear(); path.resize(n, -1);
// dfs(s, -1, t);
cout << sum - pMAX[s][t] << endl;
// int MAX = 0;
// int now = t;
// while(now != s){
// int next = path[now];
// chmax(MAX, cost[now][next]);
// now = next;
// }
// cout << sum - MAX << endl;
// rep(j, 0, path.size()){
// cout << path[j] << " ";
// }
// cout << endl;
// dijkstra(s);
// cout << d[t] << endl;
}
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
treeone |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3064 Byte |
Status |
MLE |
Exec Time |
876 ms |
Memory |
263912 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
0 / 200 |
0 / 300 |
0 / 200 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_1.txt, sample_2.txt |
subtask1 |
sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 |
sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt |
All |
sample_1.txt, sample_2.txt, sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_1.txt |
AC |
2 ms |
2432 KB |
sample_2.txt |
AC |
2 ms |
2432 KB |
subtask_1_1.txt |
AC |
3 ms |
6912 KB |
subtask_1_10.txt |
MLE |
607 ms |
256620 KB |
subtask_1_11.txt |
AC |
2 ms |
2432 KB |
subtask_1_2.txt |
AC |
527 ms |
252404 KB |
subtask_1_3.txt |
MLE |
695 ms |
262376 KB |
subtask_1_4.txt |
AC |
479 ms |
250240 KB |
subtask_1_5.txt |
AC |
521 ms |
250176 KB |
subtask_1_6.txt |
AC |
561 ms |
254320 KB |
subtask_1_7.txt |
MLE |
692 ms |
261224 KB |
subtask_1_8.txt |
AC |
471 ms |
250112 KB |
subtask_1_9.txt |
AC |
519 ms |
250748 KB |
subtask_2_1.txt |
MLE |
699 ms |
261480 KB |
subtask_2_2.txt |
MLE |
695 ms |
262504 KB |
subtask_2_3.txt |
MLE |
703 ms |
261480 KB |
subtask_2_4.txt |
MLE |
706 ms |
262376 KB |
subtask_2_5.txt |
AC |
473 ms |
250240 KB |
subtask_2_6.txt |
AC |
529 ms |
251640 KB |
subtask_2_7.txt |
AC |
569 ms |
254064 KB |
subtask_2_8.txt |
MLE |
695 ms |
262376 KB |
subtask_3_1.txt |
MLE |
876 ms |
263912 KB |
subtask_3_2.txt |
MLE |
863 ms |
263784 KB |
subtask_3_3.txt |
AC |
649 ms |
251520 KB |
subtask_3_4.txt |
AC |
697 ms |
252028 KB |
subtask_3_5.txt |
MLE |
770 ms |
258924 KB |
subtask_3_6.txt |
MLE |
822 ms |
260968 KB |
subtask_3_7.txt |
MLE |
855 ms |
262376 KB |
subtask_3_8.txt |
MLE |
857 ms |
263784 KB |