Submission #711381

#	Time	Username	Problem	Language	Result	Execution time	Memory
711381		dsyz	Ferries (NOI13_ferries)	C++17	40 / 40	284 ms	25244 KiB

ferries

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