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