oj.uz

Submission #676467

# Submission time Handle Problem Language Result Execution time Memory
676467 2022-12-31T03:32:00 Z penguin133 Ferries (NOI13_ferries) C++17
40 / 40
 246 ms 21708 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long, long long>
vector<int>v[100005], v2[100005];
int dist[100005];
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,m;
	cin >> n >> m;
	while(m--){
		int a,b,c;
		cin >> a >> b >> c;
		v[b].push_back(a);
		v2[a].push_back(c);
	}
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	pq.push({0,n});
	fill(dist, dist + n + 1, 1e18);
	dist[n] = 0;
	for(int i=1;i<=n;i++)sort(v2[i].begin(), v2[i].end());
	while(!pq.empty()){
		int x = pq.top().first, y = pq.top().second;
		pq.pop();
		if(dist[y] < x)continue;
		for(auto i : v[y]){
			if(v2[i].empty())continue;
			if(dist[i] > x + v2[i].back())dist[i] = x + v2[i].back(),pq.push({dist[i],i});
			v2[i].pop_back();
		}
	}
	cout <<dist[1];
}

Compilation message

ferries.cpp:7:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 | main(){
      | ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5168 KB Output is correct
3 Correct 10 ms 6484 KB Output is correct
4 Correct 95 ms 18760 KB Output is correct
5 Correct 99 ms 18728 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 10 ms 6448 KB Output is correct
4 Correct 48 ms 11856 KB Output is correct
5 Correct 73 ms 14496 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6484 KB Output is correct
2 Correct 17 ms 6448 KB Output is correct
3 Correct 218 ms 20536 KB Output is correct
4 Correct 206 ms 20848 KB Output is correct
5 Correct 212 ms 20032 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 20504 KB Output is correct
2 Correct 207 ms 20596 KB Output is correct
3 Correct 246 ms 21708 KB Output is correct
4 Correct 207 ms 21572 KB Output is correct
5 Correct 235 ms 21680 KB Output is correct