oj.uz

Submission #57060

# Submission time Handle Problem Language Result Execution time Memory
57060 2018-07-13T17:40:47 Z dennisstar None (KOI16_gas) C++11
0 / 100
 235 ms 25456 KB 
#include <bits/stdc++.h>
#define mkp(a,b) make_pair(a,b)
typedef long long LL;
using namespace std;
int N,M;
int P[2510];
int dist[2510][2510]; long long Dp[2510];
vector<int> R[2510], D[2510];
int arr[2510];
bool cmp(int a, int b){return P[a]>P[b];}
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > PQ;
int chk[2510];
void djk(int lev)
{
	memset(chk, 0, sizeof(chk));
	while(!PQ.empty()) PQ.pop();
	PQ.push(mkp(0,lev));
	int lv, i, ds;
	while(!PQ.empty()) {
		ds=PQ.top().first;
		lv=PQ.top().second;
		PQ.pop();
		if (chk[lv]) continue;
		dist[lev][lv]=ds;
		chk[lv]=1;
		for (i=0; i<R[lv].size(); i++) {
			if(chk[R[lv][i]]) continue;
			PQ.push(mkp(ds+D[lv][i],R[lv][i]));
		}
	}
}
int main()
{
	scanf("%d %d", &N, &M);
	int i, j, k, x, y;
	for (i=1; i<=N; i++) scanf("%d",&P[i]);
	for (i=0; i<M; i++) {
		scanf("%d %d %d", &x, &y, &j);
		R[x].push_back(y);
		R[y].push_back(x);
		D[x].push_back(j);
		D[y].push_back(j);
	}
	for (i=1; i<=N; i++) arr[i]=i;
	for (i=1; i<=N; i++) djk(i);
	sort(arr+2,arr+N,cmp);
	for (j=2; P[arr[j]]>=P[1]&&j<=N; ) j++;
	for (i=j; i<=N; i++) {
		Dp[arr[i]]=(LL)P[1]*(LL)dist[1][arr[i]];
		for (k=j; k<i; k++) {
			Dp[arr[i]]=std::min(Dp[arr[i]], Dp[arr[k]]+(LL)P[arr[k]]*dist[arr[k]][arr[i]]);
		}
	}
	printf("%lld", Dp[N]);
	return 0;
}

Compilation message

gas.cpp: In function 'void djk(int)':
gas.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i=0; i<R[lv].size(); i++) {
             ~^~~~~~~~~~~~~
gas.cpp: In function 'int main()':
gas.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
gas.cpp:36:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i=1; i<=N; i++) scanf("%d",&P[i]);
                       ~~~~~^~~~~~~~~~~~
gas.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &j);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 680 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 680 KB Output is correct
5 Correct 2 ms 680 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Incorrect 2 ms 716 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 25428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 235 ms 25456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 680 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 680 KB Output is correct
5 Correct 2 ms 680 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Incorrect 2 ms 716 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 680 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 680 KB Output is correct
5 Correct 2 ms 680 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Incorrect 2 ms 716 KB Output isn't correct
13 Halted 0 ms 0 KB -