Submission #518902

#TimeUsernameProblemLanguageResultExecution timeMemory
518902sudheerays123Ferries (NOI13_ferries)C++17
28 / 40
234 ms24396 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define ll long long int #define tc ll test;cin >> test;while(test--) #define vi vector<ll> #define pll pair<ll,ll> #define pb push_back #define mp make_pair #define INF 1e18 #define MOD 1000000007 #define ff first #define ss second #define in >> #define out << #define space << " " << #define spacef << " " #define fo(i,a,b) for(ll i = a; i <= b; i++) #define nextline out "\n" #define print(x) for(auto i : x ) cout out i spacef #define mmax(x,i) x = max(x,i) #define mmin(x,i) x = min(x,i) #define N 100005 vector<bool> visited(N,false); vi radj[N]; void dfs(ll s){ if(visited[s]) return; visited[s] = true; for(auto u : radj[s]) dfs(u); } int main() { fast; ll n,m; cin in n in m; vector<pll> adj[n+5]; fo(i,1,m){ ll a,b,c; cin in a in b in c; adj[a].pb(mp(b,c)); radj[b].pb(a); } vi indegree(n+5,0); dfs(n); fo(i,1,n){ for(auto u : radj[i]){ if(visited[i] && visited[u]) indegree[u]++; } } vi dp(n+5); // dp[i] = minimum cost to come from N to i queue<ll> q; dp[n] = 0; q.push(n); while(!q.empty()){ ll a = q.front(); q.pop(); if(a != n){ vi first; vi second; ll cnt = 0; for(auto u : adj[a]){ cnt++; if(visited[u.first]){ first.pb(dp[u.first]); second.pb(u.second); } else{ first.pb(INF); second.pb(u.second); } } if(first.size() != 0) sort(first.begin(),first.end()); if(second.size() != 0) sort(second.rbegin(),second.rend()); dp[a] = INF; fo(i,0,cnt-1) mmin(dp[a],first[i]+second[i]); } for(auto u : radj[a]){ if(!visited[u]) continue; indegree[u]--; if(!indegree[u]) q.push(u); } } cout out dp[1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...