Submission #1767937
Source Code Expand
#include <bits/stdc++.h> #define rep(i, n) for (lli i = 0; i < (n); i++) #define rrep(i, n) for (lli i = (n)-1; i >= 0; i--) using namespace std; using lli = long long int; vector<pair<lli, lli>> e[4005]; vector<pair<lli, lli>> ne[4005]; int main() { int n, m; cin >> n >> m; int a, b; lli c; rep(i, m) { cin >> a >> b >> c; a--, b--; e[a].push_back(make_pair(b, c)); e[b].push_back(make_pair(a, c)); } lli q; cin >> q; if (q != 1) return 0; cin >> a >> b; a--, b--; using p = pair<lli, pair<lli, lli>>; priority_queue<p, vector<p>, greater<p>> que; bool used[4005] = {}; que.push(make_pair(0, make_pair(a, -1))); que.push(make_pair(0, make_pair(b, -1))); lli ans = 0; while (!que.empty()) { auto cur = que.top().second; auto cost = que.top().first; que.pop(); if (used[cur.first]) continue; ans += cost; used[cur.first] = true; if (cur.second != -1) { e[cur.first].push_back(make_pair(cur.second, cost)); e[cur.second].push_back(make_pair(cur.first, cost)); } for (auto s : e[cur.first]) { que.push(make_pair(s.second, make_pair(s.first, cur.first))); } } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | uenoku |
Language | C++14 (GCC 5.4.1) |
Score | 200 |
Code Size | 1384 Byte |
Status | WA |
Exec Time | 543 ms |
Memory | 43244 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, 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 | WA | 1 ms | 384 KB |
sample_2.txt | AC | 1 ms | 384 KB |
subtask_1_1.txt | AC | 2 ms | 640 KB |
subtask_1_10.txt | AC | 267 ms | 22896 KB |
subtask_1_11.txt | AC | 1 ms | 384 KB |
subtask_1_2.txt | AC | 53 ms | 4224 KB |
subtask_1_3.txt | AC | 537 ms | 42732 KB |
subtask_1_4.txt | AC | 7 ms | 896 KB |
subtask_1_5.txt | AC | 8 ms | 896 KB |
subtask_1_6.txt | AC | 132 ms | 11768 KB |
subtask_1_7.txt | AC | 543 ms | 43244 KB |
subtask_1_8.txt | AC | 7 ms | 768 KB |
subtask_1_9.txt | AC | 15 ms | 1532 KB |
subtask_2_1.txt | WA | 376 ms | 17920 KB |
subtask_2_2.txt | WA | 376 ms | 17920 KB |
subtask_2_3.txt | WA | 384 ms | 17920 KB |
subtask_2_4.txt | WA | 372 ms | 17920 KB |
subtask_2_5.txt | WA | 5 ms | 640 KB |
subtask_2_6.txt | WA | 21 ms | 1408 KB |
subtask_2_7.txt | WA | 96 ms | 4992 KB |
subtask_2_8.txt | WA | 375 ms | 17792 KB |
subtask_3_1.txt | WA | 373 ms | 17920 KB |
subtask_3_2.txt | WA | 379 ms | 17920 KB |
subtask_3_3.txt | WA | 5 ms | 640 KB |
subtask_3_4.txt | WA | 11 ms | 1024 KB |
subtask_3_5.txt | WA | 188 ms | 9216 KB |
subtask_3_6.txt | WA | 291 ms | 17664 KB |
subtask_3_7.txt | WA | 377 ms | 17792 KB |
subtask_3_8.txt | WA | 381 ms | 17920 KB |