oj.uz

Submission #711381

# Submission time Handle Problem Language Result Execution time Memory
711381 2023-03-16T18:55:01 Z dsyz Ferries (NOI13_ferries) C++17
40 / 40
 284 ms 25244 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M;
	cin>>N>>M;
	vector<pair<ll,ll> > fromn[N];
	priority_queue<ll> in[N];//unassigned costs of incoming edges to i
	for(ll i = 0;i < M;i++){
		ll a,b,c;
		cin>>a>>b>>c;
		a--;
		b--;
		fromn[b].push_back(make_pair(c,a));
		in[a].push(c); //in the original direction
	}
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
	ll dist[N];
	memset(dist,-1,sizeof(dist));
	pq.push(make_pair(0,N - 1));
	dist[N - 1] = 0;
	while(!pq.empty()){
		pair<ll,ll> x = pq.top();
		pq.pop();
		if(x.first != dist[x.second]){
			continue;
		}
		for(auto u : fromn[x.second]){
			ll maximum = in[u.second].top();
			u.first = maximum;
			in[u.second].pop();
			if(dist[u.second] == -1 || dist[u.second] > dist[x.second] + u.first){
				dist[u.second] = dist[x.second] + u.first;
				pq.push(make_pair(dist[u.second],u.second));
			}
		}
	}
	cout<<dist[0]<<'\n';			
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 13 ms 2504 KB Output is correct
4 Correct 124 ms 21268 KB Output is correct
5 Correct 112 ms 21168 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 428 KB Output is correct
3 Correct 8 ms 2376 KB Output is correct
4 Correct 50 ms 10688 KB Output is correct
5 Correct 98 ms 15388 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2552 KB Output is correct
2 Correct 19 ms 2600 KB Output is correct
3 Correct 216 ms 24080 KB Output is correct
4 Correct 284 ms 24392 KB Output is correct
5 Correct 229 ms 23560 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 23992 KB Output is correct
2 Correct 222 ms 24132 KB Output is correct
3 Correct 255 ms 25244 KB Output is correct
4 Correct 251 ms 25128 KB Output is correct
5 Correct 246 ms 25244 KB Output is correct