oj.uz

Submission #258509

# Submission time Handle Problem Language Result Execution time Memory
258509 2020-08-06T05:14:51 Z 송준혁(#5060) Park (BOI16_park) C++17
0 / 100
 10 ms 9984 KB 
#include <bits/stdc++.h>
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
#define mup(a,x) a=min(a,x)
#define Mup(a,x) a=max(a,x)
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;

int N, M;
LL C, D[202020], ans, sum;
vector<pii> adj[202020], V;
priority_queue<pii> PQ;

int main(){
	scanf("%d %d %lld", &N, &M, &C);
	for (int i=1; i<=M; i++){
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		adj[u].pb(pii(v, w)), adj[v].pb(pii(u, w));
		sum += w;
	}
	for (int i=1; i<=N; i++) D[i]=INF;
	PQ.push(pii(0, 1));
	while (!PQ.empty()){
		LL u, x;
		tie(x, u) = PQ.top();
		PQ.pop();
		if (D[u] != INF) continue;
		D[u] = -x;
		for (pii v : adj[u]) PQ.push(pii(x-v.se, v.fi));
	}
	for (int u=1; u<=N; u++) for (pii v : adj[u]) if (u<v.fi) V.pb(pii(max(D[u], D[v.fi]), v.se));
	sort(V.begin(), V.end());
	LL s=0;
	ans = sum;
	for (pii t : V){
		s += t.se;
		ans = min(ans, sum+C*t.fi-s);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %lld", &N, &M, &C);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -