Submission #560076

#	Time	Username	Problem	Language	Result	Execution time	Memory
560076		Garguy22	Ferries (NOI13_ferries)	C++17	40 / 40	416 ms	21748 KiB

ferries

#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 / 7
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12