oj.uz

Submission #269775

# Submission time Handle Problem Language Result Execution time Memory
269775 2020-08-17T10:07:31 Z sean9892 None (KOI16_gas) C++14
34 / 100
 21 ms 25376 KB 
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using dat=pair<int,pii>;
#define fi first
#define se second

vector<pii> g[2510];
int cst[2510];
int dst[2510][2510];

int main(void){
	ios::sync_with_stdio(0);cin.tie(0);
	
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>cst[i];
	}
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		g[a].emplace_back(b,c);
		g[b].emplace_back(a,c);
	}
	
	memset(dst,0x3f,sizeof(dst));
	dst[1][cst[1]]=0;
	priority_queue<dat> q;
	
	int res=0x3f3f3f3f;
	
	#define pushDat(d,x,c) q.push(dat(-(d),pii(x,c)))
	#define popDat(d,x,c) do{d=-q.top().fi;x=q.top().se.fi;c=q.top().se.se;q.pop();}while(0);
	
	pushDat(0,1,cst[1]);
	while(!q.empty()){
		int d,x,c;
		popDat(d,x,c);
		if(dst[x][c]<d)continue;
		if(x==n){
			res=min(res,d);
		}
		for(auto& e:g[x]){
			int i,w;
			tie(i,w)=e;
			if(dst[i][min(c,cst[i])]>d+c*w){
				dst[i][min(c,cst[i])]=d+c*w;
				pushDat(d+c*w,i,min(c,cst[i]));
			}
		}
	}
	
	#undef pushDat
	#undef popDat
	
	cout<<res;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25088 KB Output is correct
2 Correct 15 ms 25088 KB Output is correct
3 Correct 15 ms 25088 KB Output is correct
4 Correct 15 ms 25088 KB Output is correct
5 Correct 16 ms 25088 KB Output is correct
6 Correct 15 ms 25088 KB Output is correct
7 Correct 15 ms 25088 KB Output is correct
8 Correct 18 ms 25088 KB Output is correct
9 Correct 15 ms 25088 KB Output is correct
10 Correct 15 ms 25088 KB Output is correct
11 Correct 15 ms 25088 KB Output is correct
12 Correct 15 ms 25088 KB Output is correct
13 Correct 15 ms 25088 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 25216 KB Output is correct
2 Correct 16 ms 25176 KB Output is correct
3 Correct 17 ms 25216 KB Output is correct
4 Correct 18 ms 25216 KB Output is correct
5 Incorrect 20 ms 25216 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25216 KB Output is correct
2 Correct 18 ms 25344 KB Output is correct
3 Correct 19 ms 25376 KB Output is correct
4 Correct 18 ms 25344 KB Output is correct
5 Correct 17 ms 25344 KB Output is correct
6 Correct 17 ms 25344 KB Output is correct
7 Correct 17 ms 25344 KB Output is correct
8 Correct 19 ms 25344 KB Output is correct
9 Correct 17 ms 25216 KB Output is correct
10 Correct 17 ms 25216 KB Output is correct
11 Correct 17 ms 25216 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25088 KB Output is correct
2 Correct 15 ms 25088 KB Output is correct
3 Correct 15 ms 25088 KB Output is correct
4 Correct 15 ms 25088 KB Output is correct
5 Correct 16 ms 25088 KB Output is correct
6 Correct 15 ms 25088 KB Output is correct
7 Correct 15 ms 25088 KB Output is correct
8 Correct 18 ms 25088 KB Output is correct
9 Correct 15 ms 25088 KB Output is correct
10 Correct 15 ms 25088 KB Output is correct
11 Correct 15 ms 25088 KB Output is correct
12 Correct 15 ms 25088 KB Output is correct
13 Correct 15 ms 25088 KB Output is correct
14 Incorrect 15 ms 25088 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25088 KB Output is correct
2 Correct 15 ms 25088 KB Output is correct
3 Correct 15 ms 25088 KB Output is correct
4 Correct 15 ms 25088 KB Output is correct
5 Correct 16 ms 25088 KB Output is correct
6 Correct 15 ms 25088 KB Output is correct
7 Correct 15 ms 25088 KB Output is correct
8 Correct 18 ms 25088 KB Output is correct
9 Correct 15 ms 25088 KB Output is correct
10 Correct 15 ms 25088 KB Output is correct
11 Correct 15 ms 25088 KB Output is correct
12 Correct 15 ms 25088 KB Output is correct
13 Correct 15 ms 25088 KB Output is correct
14 Correct 16 ms 25216 KB Output is correct
15 Correct 16 ms 25176 KB Output is correct
16 Correct 17 ms 25216 KB Output is correct
17 Correct 18 ms 25216 KB Output is correct
18 Incorrect 20 ms 25216 KB Output isn't correct
19 Halted 0 ms 0 KB -