This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
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);
multiset<ll, greater<int>> ts;
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;
ts.clear();
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";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |