# Untitled

unknown
c_cpp
12 days ago
2.3 kB
2
Indexable
Never
```/// I am snatchin chains and burnin' tattoos
#include <bits/stdc++.h>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i, a, b) for (int i = a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define mp(x, y) make_pair(x, y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll

using ll = long long;
using ii = pair<int, int>;
using ull = unsigned long long;

const int N = 1e6 + 5, A = 26 * 26, LG = 19, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-7;
vector<vector<int>> go[N];
int dp[205][205];
int cost[205][205], del[205];
int n, m;
int a[205];
int solve(int index, int prv) {
if(index == n) return 0;
int &ret = dp[index][prv];
if(~ret)    return ret;
ret = 1e17;
if(a[index] >= prv) ret = min(ret, solve(index + 1, a[index]));
ret = min(ret, solve(index + 1, prv) + del[a[index]]);
f(i,1,201) if(i >= prv)ret = min(ret, solve(index+1,i)+cost[a[index]][i]);
f(i,1,201) ret = min(ret, solve(index+1,prv)+cost[a[index]][i]+del[i]);
return ret;
}
void doWork() {
memset(dp,-1,sizeof dp);
cin >> n >> m;
f(i,0,n)    cin >> a[i];
f(i,0,205)
f(j,0,205) cost[i][j] = 1e17;
f(i,0,205)cost[i][i] = 0, del[i]=1e17;
f(i,0,m) {
int tp;
cin >> tp;
if(tp == 1) {
int x, y, c;
cin >> x >> y >> c;
cost[x][y] = min(cost[x][y], c);
}   else {
int x, c;
cin >> x >> c;
del[x] = min(del[x], c);
}
}
f(k,0,205)
f(i,0,205)
f(j,0,205)cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
int ans = solve(0,0);
if(ans > 1e16) cout << "-1\n";
else cout << ans << "\n";
}

int32_t main() {
#ifdef LOCAL
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif

int t = 1;
// cin >> t;
while (t--) {
doWork();
}
}```