Submission #676467

#	Time	Username	Problem	Language	Result	Execution time	Memory
676467		penguin133	Ferries (NOI13_ferries)	C++17	40 / 40	246 ms	21708 KiB

ferries

#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 (stderr)

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

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12