oj.uz

Submission #560076

# Submission time Handle Problem Language Result Execution time Memory
560076 2022-05-11T03:36:38 Z Garguy22 Ferries (NOI13_ferries) C++17
40 / 40
 416 ms 21748 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define mp make_pair

const int MAXN = 1e5 + 7;
const ll INF = 1e18 + 7;

vector<ll> adj[MAXN], wt[MAXN];
ll dis[MAXN];

int main(){
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int x, y, z;
		cin >> x >> y >> z;
		adj[y].pb(x);
		wt[x].pb(z);
	}
	for(int i = 1; i <= n; i++)
		sort(wt[i].begin(), wt[i].end());
	for(int i = 1; i <= n; i++)
		dis[i] = INF;
	priority_queue<pll , vector<pll>, greater<pll> > q;
	q.push(mp(0, n));
	dis[n] = 0;
	while(!q.empty()){
		pll x = q.top();
		q.pop();
		ll d = x.first, u = x.second;
		if(d <= dis[u]){
			for(int v : adj[u]){
				ll temp = wt[v].back();
				wt[v].pop_back();
				if(dis[v] > d + temp){
					dis[v] = d + temp;
					q.push(mp(dis[v], v));
				}
			}
		}
	}
	cout << dis[1] << endl;

	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5144 KB Output is correct
3 Correct 19 ms 6504 KB Output is correct
4 Correct 196 ms 18800 KB Output is correct
5 Correct 205 ms 18700 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 20 ms 6416 KB Output is correct
4 Correct 92 ms 11816 KB Output is correct
5 Correct 137 ms 14484 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6404 KB Output is correct
2 Correct 30 ms 6416 KB Output is correct
3 Correct 381 ms 20408 KB Output is correct
4 Correct 411 ms 20720 KB Output is correct
5 Correct 383 ms 20060 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 20436 KB Output is correct
2 Correct 372 ms 20484 KB Output is correct
3 Correct 399 ms 21748 KB Output is correct
4 Correct 396 ms 21692 KB Output is correct
5 Correct 416 ms 21744 KB Output is correct