Submission #996304


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];

//           cost,   ,  dst
vector<pair<long long, long long> >tree[4005];

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 != 1){
		return 1;
	}
	
	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[0]));
	Q.push(make_pair(0, T[0]));

	while(!Q.empty() && 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 < 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, next));
		}
	}
	cout << ans << endl;










}

Submission Info

Submission Time
Task A - Graph
User motomuman
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1547 Byte
Status RE
Exec Time 482 ms
Memory 26220 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 200 / 200 0 / 300 0 / 200
Status
AC × 1
RE × 1
AC × 12
AC × 12
RE × 9
AC × 12
RE × 17
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 RE 3 ms 384 KB
sample_2.txt AC 3 ms 384 KB
subtask_1_1.txt AC 4 ms 384 KB
subtask_1_10.txt AC 245 ms 13424 KB
subtask_1_11.txt AC 3 ms 384 KB
subtask_1_2.txt AC 57 ms 3576 KB
subtask_1_3.txt AC 480 ms 26104 KB
subtask_1_4.txt AC 9 ms 768 KB
subtask_1_5.txt AC 10 ms 768 KB
subtask_1_6.txt AC 128 ms 7028 KB
subtask_1_7.txt AC 482 ms 26220 KB
subtask_1_8.txt AC 9 ms 768 KB
subtask_1_9.txt AC 18 ms 1152 KB
subtask_2_1.txt RE 385 ms 17920 KB
subtask_2_2.txt RE 386 ms 17792 KB
subtask_2_3.txt RE 386 ms 17920 KB
subtask_2_4.txt RE 386 ms 17792 KB
subtask_2_5.txt RE 8 ms 640 KB
subtask_2_6.txt RE 25 ms 1408 KB
subtask_2_7.txt RE 100 ms 4992 KB
subtask_2_8.txt RE 384 ms 17792 KB
subtask_3_1.txt RE 441 ms 19328 KB
subtask_3_2.txt RE 431 ms 19456 KB
subtask_3_3.txt RE 55 ms 2048 KB
subtask_3_4.txt RE 61 ms 2432 KB
subtask_3_5.txt RE 241 ms 10752 KB
subtask_3_6.txt RE 342 ms 19200 KB
subtask_3_7.txt RE 433 ms 19328 KB
subtask_3_8.txt RE 439 ms 19328 KB