Submission #525614

#	Time	Username	Problem	Language	Result	Execution time	Memory
525614		aadit_ambadkar	Ferries (NOI13_ferries)	C++11	28 / 40	277 ms	29760 KiB

ferries

/*
    This code belongs to Aadit Ambadkar
    Date: 2022-02-11 22:17:56
    Problem: fer
*/
#include <bits/stdc++.h>
using namespace::std;

typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define MOD 1000000007
#define INF 1000000000000000007LL
#define FF first
#define SS second

const int MX = 1e5+5;
int n, m; 
vector<int> adj[MX];
multiset<ll> cs[MX];
vector<int> vis(MX, 0);  // three state dfs (white grey black)
vector<ll> mn(MX, INF);

ll dfs(int node) {
    if (vis[node]==1) return INF;
    else if (vis[node]==2) return mn[node];
    if (node==n-1) {
        vis[node]=2;
        mn[node]=0;
        return 0;
    }
    vis[node]=1;
    multiset<ll, greater<int>> ts;
    for (auto i : adj[node]) {
        ll j = dfs(i);
        // assert(j==mn[i]);
        ts.insert(j);
    }
    
    // for (auto i : adj[node]) {
    //     cout << i << " ";
    // }
    // cout << "\n";
    // if (node == 0) {
    //     for (auto i : ts) {
    //         cout << i << " ";
    //     }
    //     cout << "\n";
    // }

    auto i1 = ts.begin(), i2 = cs[node].begin();
    ll ans = MOD;
    while (i1!=ts.end() && i2 != cs[node].end()) {
        ans = min(ans, (*(i1))+(*(i2)));
        i1++;
        i2++;
    }
    mn[node]=ans;
    // cout << "MN of " << node << " is " << mn[node] << "\n";
    vis[node]=2;
    return ans;
}

int main() {
    fastio;
    cin >> n >> m;
    F0R(i, m) {
        int a, b; ll c; cin >> a >> b >> c; a--; b--;
        adj[a].pb(b);
        cs[a].insert(c);
    }
    cout << dfs(0) << "\n";

    // F0R(i, n) {
    //     cout << mn[i] << " ";
    // }
    // cout << "\n";

}

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