Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int l=0;
- int n=0;
- int a=0;
- string s;
- int i=0;
- int j=0;
- char b;
- char c;
- bool check = false;
- int p=0;
- int curr=0;
- int curry=0;
- int curryy=0;
- int ans = 0;
- cin>>l>>n;
- vector<vector<int>> vec(26, vector<int>(26, 1e16));
- vector<vector<bool>> veco(26, vector<bool>(26, false));
- cin>>s;
- while (n--) {
- cin>>b>>c>>a;
- vec.at(b - 'a').at(c - 'a') = min(vec.at(b - 'a').at(c - 'a'), a);
- veco.at(b - 'a').at(c - 'a') = true;
- }
- for (i=0;i<26;i++) {
- vec.at(i).at(i) = 0;
- veco.at(i).at(i) = true;
- }
- for (a=0;a<26;a++) {
- for (i=0;i<26;i++) {
- for (j=0;j<26;j++)
- vec.at(i).at(j) = min(vec.at(i).at(j), (vec.at(i).at(a) + vec.at(a).at(j)));
- }
- }
- for (i=0;i<26;i++) {
- for(j=0;j<26;j++) {
- if (vec.at(i).at(j) < (int)1e16)
- veco.at(i).at(j) = true;
- }
- }
- p=(l/2);
- for (i=0;i<p;i++) {
- curr = LLONG_MAX;
- curry = s[i] - 'a';
- curryy = s[l - i - 1] - 'a';
- for (j=0;j<26;j++) {
- if (veco.at(curry).at(j) && veco.at(curryy).at(j)) {
- check = true;
- curr = min(curr, vec.at(curry).at(j) + vec.at(curryy).at(j));
- }
- }
- if(!check) {
- cout<<"-1"<<endl;
- return 0;
- }
- ans += curr;
- }
- cout<<ans<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
