Consider painting Vertices \(0,1,\ldots,N\) red or blue, and minimizing the sum of edges that connect the vertices with the same color.

Without loss of generality, Vertex \(0\) can assumed to be red.

Here, let us ignore the edge between Vertex \(1\) and Vertex \(N\), and consider the following \(dp\) (Dynamic Programming).

\(dp[i][j][k] :=\) Minimum sum of weights of edges after painting Vertex \(1\) through \(i\)

Here, Vertex \(i\) are painted in color \(j\) and Vertex \(1\) are painted in color \(k\) (where \(j\) and \(k\) has a value \(0\) for red and \(1\) for blue).

\(dp[i]\) can be computed from \(dp[i-1]\). (If you are not sure with transitions or initial values, refer to the sample code below as well.)

Finally, the answer can be obtained from \(dp[N]\), taking into account the edge connecting Vertex \(1\) and Vertex \(N\).

The complexity is \(O(N)\).

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
void chmin(ll &a,ll b){a = min(a,b);}
ll inf = 1e18;

signed main(){
    ll n;cin>>n;
    vector<ll> a(n+1),b(n+1);
    rep(i,1,n)cin>>a[i];
    rep(i,1,n)cin>>b[i];
    vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>>(2,vector<ll>(2,inf)));
    dp[1][0][0] = a[1];
    dp[1][1][1] = 0;
    rep(i,2,n)rep(j,0,1)rep(k,0,1)rep(prej,0,1){
        chmin(dp[i][j][k],dp[i-1][prej][k] + (j==0?a[i]:0) + (j==prej?b[i-1]:0));
    }
    ll ans = inf;
    rep(j,0,1)rep(k,0,1)chmin(ans,dp[n][j][k] + (j==k?b[n]:0));
    cout<<ans<<endl;
    return 0;
}