Submission #138681

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138681	2019-07-30T08:31:20 Z	이온조(#3319)	Farm and factory (CERC12_F)	C++14	0 / 1	47 ms	2808 KB

F

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second

int N;
vector<pii> G[100009];

vector<long long> dijk(int st) {
	vector<long long> D(N+1, 1LL * 1e18);
	priority_queue<pair<long long, int> > pq; pq.push({0, st}); D[st] = 0;
	while(pq.size()) {
		long long c; int n; tie(c, n) = pq.top(); c *= -1; pq.pop();
		if(c != D[n]) continue;
		for(auto& it: G[n]) {
			if(D[it.X] > D[n] + it.Y) {
				D[it.X] = D[n] + it.Y;
				pq.push({-D[it.X], it.X});
			}
		}
	}
	return D;
}

int main() {
	int T; scanf("%d",&T);
	while(T--) {
		int M; scanf("%d%d",&N,&M);
		for(int i=1; i<=N; i++) {
			G[i].clear();
			G[i].shrink_to_fit();
		}
		for(int i=0; i<M; i++) {
			int u, v, w; scanf("%d%d%d",&u,&v,&w);
			G[u].push_back({v, w});
			G[v].push_back({u, w});
		}
		vector<long long> D1 = dijk(1), D2 = dijk(2);
		long long s = -1LL * (N-2) * D1[2];
		for(int i=1; i<=N; i++) s += D1[i] + D2[i];
		printf("%.10f\n", (double)s / 2 / N);
	}
	return 0;
}

Compilation message

F.cpp: In function 'int main()':
F.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int T; scanf("%d",&T);
         ~~~~~^~~~~~~~~
F.cpp:29:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int M; scanf("%d%d",&N,&M);
          ~~~~~^~~~~~~~~~~~~~
F.cpp:35:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int u, v, w; scanf("%d%d%d",&u,&v,&w);
                 ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Incorrect	47 ms	2808 KB	Output isn't correct
3	Halted	0 ms	0 KB	-