This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define tj
#ifdef tj
#include "shortcut.h"
#endif
#include <bits/stdc++.h>
//#define DEBUG 1106
//#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define p_q priority_queue
#define m_p make_pair
#define pii pair<ll,ll>
#define endl '\n'
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define forn(i,n) for (int i = 0; i < n; i++)
#define forn1(i,n) for (int i = 1; i <= n; i++)
#define all(x) x.begin(),x.end()
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#ifdef DEBUG
#define debug(x) cout << #x << ": " << x << endl;
#else
#define debug(x) 1106;
#endif
using namespace std;
const int N = 50;
const int inf = 1e9;
const ll INF = 1e18;
const int MOD = 1e9+7;
int n;
vector<pii> G[N];
ll dis[N];
long long src(int x, int dest) {
p_q<pii, vector<pii>, greater<pii>> pq;
memset(dis,-1,sizeof(dis));
pq.push(m_p(0, x));
dis[x] = 0;
ll ans = 0;
while (!pq.empty()) {
pii c = pq.top();
pq.pop();
if (dis[c.sd] != c.ft) continue;
for (auto i : G[c.sd]) {
if (dis[i.ft] == -1 || dis[i.ft] > i.sd+c.ft) {
dis[i.ft] = i.sd+c.ft;
chmax(ans,dis[i.ft]);
pq.push(m_p(dis[i.ft], i.ft));
}
}
}
return ans;
}
long long find_diameter() {
ll ans = 0;
forn(i,n*2+2) {
chmax(ans,src(i,0));
}
return ans;
}
long long find_shortcut(int n_, vector<int> l, vector<int> d, int c) {
n = n_;
forn(i,n) {
if(i!=n-1) {
G[i].pb({i+1,l[i]});
G[i+1].pb({i,l[i]});
}
if(d[i]) {
G[i].pb({i+n,d[i]});
G[i+n].pb({i,d[i]});
}
}
ll ans = INF;
for(int i = 0; i < n-1; i++) {
for(int j = i+1; j <= n-1; j++) {
G[i].pb({j,c});
G[j].pb({i,c});
ll t = find_diameter();
chmin(ans,t);
G[i].pop_back();
G[j].pop_back();
}
}
return ans;
}
#ifndef tj
int main() {
int n, c;
assert(2 == scanf("%d%d", &n, &c));
std::vector<int> l(n - 1);
std::vector<int> d(n);
for (int i = 0; i < n - 1; i++)
assert(1 == scanf("%d", &l[i]));
for (int i = 0; i < n; i++)
assert(1 == scanf("%d", &d[i]));
long long t = find_shortcut(n, l, d, c);
printf("%lld\n", t);
return 0;
}
#endif
# | 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... |
# | 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... |