Submission #1628887
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;
void dfs(int now, int pre, int dest){
// cout << " " << now << " " << pre << endl;
path[now] = pre;
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, dest);
}
}
int cost[4010][4010];
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;
cin >> q;
rep(i, 0, q){
int s, t;
cin >> s >> t;
s--; t--;
path.clear(); path.resize(n, -1);
dfs(s, -1, t);
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 |
500 |
Code Size |
2807 Byte |
Status |
TLE |
Exec Time |
3156 ms |
Memory |
140012 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
200 / 200 |
300 / 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 |
1 ms |
384 KB |
sample_2.txt |
AC |
1 ms |
384 KB |
subtask_1_1.txt |
AC |
2 ms |
2816 KB |
subtask_1_10.txt |
AC |
113 ms |
133232 KB |
subtask_1_11.txt |
AC |
1 ms |
384 KB |
subtask_1_2.txt |
AC |
44 ms |
126968 KB |
subtask_1_3.txt |
AC |
205 ms |
138988 KB |
subtask_1_4.txt |
AC |
28 ms |
124288 KB |
subtask_1_5.txt |
AC |
28 ms |
124352 KB |
subtask_1_6.txt |
AC |
70 ms |
128884 KB |
subtask_1_7.txt |
AC |
202 ms |
140012 KB |
subtask_1_8.txt |
AC |
28 ms |
124160 KB |
subtask_1_9.txt |
AC |
30 ms |
124924 KB |
subtask_2_1.txt |
AC |
533 ms |
138604 KB |
subtask_2_2.txt |
AC |
530 ms |
139244 KB |
subtask_2_3.txt |
AC |
525 ms |
139500 KB |
subtask_2_4.txt |
AC |
527 ms |
138860 KB |
subtask_2_5.txt |
AC |
326 ms |
124416 KB |
subtask_2_6.txt |
AC |
371 ms |
125944 KB |
subtask_2_7.txt |
AC |
392 ms |
129908 KB |
subtask_2_8.txt |
AC |
524 ms |
139372 KB |
subtask_3_1.txt |
TLE |
3156 ms |
139372 KB |
subtask_3_2.txt |
TLE |
3156 ms |
139372 KB |
subtask_3_3.txt |
TLE |
3156 ms |
124800 KB |
subtask_3_4.txt |
TLE |
3156 ms |
125308 KB |
subtask_3_5.txt |
TLE |
3156 ms |
132592 KB |
subtask_3_6.txt |
TLE |
3156 ms |
139884 KB |
subtask_3_7.txt |
TLE |
3156 ms |
138732 KB |
subtask_3_8.txt |
TLE |
3156 ms |
138220 KB |