Submission #996913


Source Code Expand

    #include <string>
    #include <vector>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    #include <map>
    #include <set>
    #include <iostream>
    #include <sstream>
    #include <cstring>
    #include <numeric>
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> pii;
    #define F0(i,n) for (int i = 0; i < n; i++)
    #define F1(i,n) for (int i = 1; i <= n; i++)
    #define CL(a,x) memset(x, a, sizeof(x));
    #define SZ(x) ((int)x.size())
    const double eps = 1e-10;
    const int inf = 1000000009;
    int i, j, k, m, n, l;
    int ans;
    string s;
    const int N = 5000;
    int a[N], b[N], id[N], p[N];
    int c[N][N], u[N], best[N];
     
     
    int main() {
    	//freopen("x.in", "r", stdin);
     
    	cin >> n >> m;
    	F0(i, m) {
    		cin >> a[i] >> b[i] >> j;
if (c[a[i]][b[i]] == 0 || c[a[i]][b[i]] > j)
    		c[a[i]][b[i]] = c[b[i]][a[i]] = j;
     	}
     
    	int Q, S, T;
    	cin >> Q;
    	while (Q--) {
    		cin >> S >> T;
     
    		set<pii> SE;
    		F1(i, n) if (i != S && i != T) {
  best[i] = min(c[S][i], c[T][i]);
    	 SE.insert(pii(best[i], i));
    			u[i] = 0;
    		}
u[S] = u[T] = 1;
     
    		ll ans = 0;
    		F0(i, n - 2) {
    			pii p = *SE.begin(); SE.erase(SE.begin());
    			ans += p.first;
    			u[p.second] = 1;
    			F1(i, n) if (!u[i]) {
    				if (c[p.second][i] < best[i]) {
SE.erase(SE.find(pii(best[i], i)));
best[i] = c[p.second][i];
SE.insert(pii(best[i], i));
}
    			}
     
    		}
    		cout << ans << endl;
    	}
    	
    	return 0;
    }

Submission Info

Submission Time
Task A - Graph
User USA
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1693 Byte
Status WA
Exec Time 3157 ms
Memory 31360 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 300 0 / 200
Status
AC × 1
WA × 1
AC × 2
WA × 4
RE × 6
AC × 2
WA × 5
TLE × 1
RE × 13
AC × 2
WA × 5
TLE × 2
RE × 20
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 WA 3 ms 256 KB
sample_2.txt AC 3 ms 256 KB
subtask_1_1.txt WA 4 ms 768 KB
subtask_1_10.txt RE 165 ms 30976 KB
subtask_1_11.txt AC 3 ms 256 KB
subtask_1_2.txt RE 165 ms 31232 KB
subtask_1_3.txt RE 164 ms 31104 KB
subtask_1_4.txt WA 75 ms 26624 KB
subtask_1_5.txt WA 81 ms 31360 KB
subtask_1_6.txt RE 163 ms 31232 KB
subtask_1_7.txt RE 164 ms 30976 KB
subtask_1_8.txt WA 75 ms 26496 KB
subtask_1_9.txt RE 163 ms 31104 KB
subtask_2_1.txt RE 165 ms 30848 KB
subtask_2_2.txt RE 163 ms 30848 KB
subtask_2_3.txt RE 166 ms 31104 KB
subtask_2_4.txt RE 162 ms 30976 KB
subtask_2_5.txt TLE 3157 ms 26624 KB
subtask_2_6.txt RE 165 ms 30848 KB
subtask_2_7.txt RE 162 ms 30720 KB
subtask_2_8.txt RE 164 ms 31232 KB
subtask_3_1.txt RE 162 ms 30976 KB
subtask_3_2.txt RE 163 ms 30976 KB
subtask_3_3.txt TLE 3157 ms 26624 KB
subtask_3_4.txt RE 166 ms 30976 KB
subtask_3_5.txt RE 165 ms 31104 KB
subtask_3_6.txt RE 165 ms 30848 KB
subtask_3_7.txt RE 166 ms 31104 KB
subtask_3_8.txt RE 166 ms 30848 KB