Submission #998689
Source Code Expand
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
#define DIV 1000000007
using namespace std;
long long N, M, Q;
long long S[100005];
long long T[100005];
long long hen;
// cost, , dst
vector<pair<long long, long long> >tree[4005];
// cost, , dst
vector<pair<long long, long long> >ttree[4005];
void solve(long long s, long long t){
set<long long> done;
// cost , dst
priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > > Q;
long long ans = 0;
Q.push(make_pair(0, s));
Q.push(make_pair(0, t));
while(done.size() < N){
long long cost, dst;
cost = Q.top().first;
dst = Q.top().second;
Q.pop();
if(done.count(dst) != 0){
continue;
}
ans += cost;
done.insert(dst);
for(int i = 0; i < ttree[dst].size(); i++){
long long ncost = ttree[dst][i].first;
long long next = ttree[dst][i].second;
if(done.count(next) != 0){
continue;
}
Q.push(make_pair(ncost, next));
}
}
cout << ans << endl;
}
void prepare(){
set<long long> done;
// cost , src , dst
priority_queue<pair<long long, pair<long long, long long> >, vector<pair<long long, pair<long long, long long> > >, greater<pair<long long, pair<long long, long long> > > > Q;
Q.push(make_pair(0, make_pair(-1, 0)));
while(done.size() < N){
long long cost, src, dst;
cost = Q.top().first;
src = Q.top().second.first;
dst = Q.top().second.second;
Q.pop();
if(done.count(dst) != 0){
continue;
}
done.insert(dst);
if(src != -1){
ttree[src].push_back(make_pair(cost, dst));
ttree[dst].push_back(make_pair(cost, src));
hen++;
}
for(int i = 0; i < tree[dst].size(); i++){
long long ncost = tree[dst][i].first;
long long next = tree[dst][i].second;
if(done.count(next) != 0){
continue;
}
Q.push(make_pair(ncost, make_pair(dst, next)));
}
}
}
int main(){
cin >> N >> M;
for(int i = 0; i < M; i++){
long long a, b, c;
cin >> a >> b >> c;
a--;b--;
tree[a].push_back(make_pair(c, b));
tree[b].push_back(make_pair(c, a));
}
cin >> Q;
for(int i = 0; i < Q; i++){
cin >> S[i] >> T[i];
S[i]--;T[i]--;
}
if(Q > 3000){
return 1;
}
prepare();
//cout << "hen = " << hen <<endl;
if(hen > N){
return 1;
}
for(int i = 0; i < Q; i++){
solve(S[i], T[i]);
}
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
motomuman |
Language |
C++14 (GCC 5.4.1) |
Score |
200 |
Code Size |
2697 Byte |
Status |
TLE |
Exec Time |
3155 ms |
Memory |
30452 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
200 / 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, 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 |
3 ms |
384 KB |
sample_2.txt |
AC |
2 ms |
384 KB |
subtask_1_1.txt |
AC |
4 ms |
512 KB |
subtask_1_10.txt |
AC |
253 ms |
15476 KB |
subtask_1_11.txt |
AC |
3 ms |
384 KB |
subtask_1_2.txt |
AC |
61 ms |
4220 KB |
subtask_1_3.txt |
AC |
493 ms |
30320 KB |
subtask_1_4.txt |
AC |
11 ms |
1024 KB |
subtask_1_5.txt |
AC |
13 ms |
1152 KB |
subtask_1_6.txt |
AC |
135 ms |
8184 KB |
subtask_1_7.txt |
AC |
497 ms |
30320 KB |
subtask_1_8.txt |
AC |
11 ms |
1024 KB |
subtask_1_9.txt |
AC |
21 ms |
1396 KB |
subtask_2_1.txt |
TLE |
3155 ms |
30452 KB |
subtask_2_2.txt |
TLE |
3155 ms |
30324 KB |
subtask_2_3.txt |
TLE |
3155 ms |
30452 KB |
subtask_2_4.txt |
TLE |
3155 ms |
30328 KB |
subtask_2_5.txt |
TLE |
3154 ms |
1152 KB |
subtask_2_6.txt |
TLE |
3154 ms |
2176 KB |
subtask_2_7.txt |
TLE |
3154 ms |
8180 KB |
subtask_2_8.txt |
TLE |
3155 ms |
30320 KB |
subtask_3_1.txt |
RE |
429 ms |
19456 KB |
subtask_3_2.txt |
RE |
428 ms |
19456 KB |
subtask_3_3.txt |
RE |
54 ms |
2176 KB |
subtask_3_4.txt |
RE |
60 ms |
2560 KB |
subtask_3_5.txt |
RE |
239 ms |
10752 KB |
subtask_3_6.txt |
RE |
342 ms |
19200 KB |
subtask_3_7.txt |
RE |
431 ms |
19456 KB |
subtask_3_8.txt |
RE |
436 ms |
19456 KB |