This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 302;
const int M_MAX = 302;
int n, m;
string a, b;
int dp[M_MAX][N_MAX];
struct State
{
int pref;
int pos;
};
struct Path
{
State s;
int len;
};
bool operator < (const Path &a, const Path &b)
{
return a.len > b.len;
}
priority_queue <Path> pq;
bool visited[M_MAX][N_MAX];
vector <int> vch[26];
void Dijkstra ()
{
for(int i = 1; i <= n; i++)
if(a[i] == b[1])
pq.push(Path{State{1, i}, 0});
while(pq.empty() == false)
{
Path p = pq.top();
pq.pop();
if(visited[p.s.pref][p.s.pos] == true)
continue;
visited[p.s.pref][p.s.pos] = true;
dp[p.s.pref][p.s.pos] = p.len;
if(p.s.pref == m)
continue;
if(p.s.pos > 1 && a[p.s.pos - 1] == b[p.s.pref + 1] && visited[p.s.pref + 1][p.s.pos - 1] == false)
pq.push(Path{State{p.s.pref + 1, p.s.pos - 1}, p.len + 1});
if(p.s.pos < n && a[p.s.pos + 1] == b[p.s.pref + 1] && visited[p.s.pref + 1][p.s.pos + 1] == false)
pq.push(Path{State{p.s.pref + 1, p.s.pos + 1}, p.len + 1});
for(int pos1 : vch[a[p.s.pos] - 'a'])
if(pos1 + p.s.pos)
{
if(visited[p.s.pos][pos1] == false)
pq.push(Path{State{p.s.pref, pos1}, p.len + abs(p.s.pos - pos1)});
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cin >> a >> b;
a = " " + a;
b = " " + b;
for(int i = 1; i <= n; i++)
vch[a[i] - 'a'].push_back(i);
Dijkstra();
int ans = INT_MAX;
for(int i = 1; i <= n; i++)
if(visited[m][i] == true)
ans = min(ans, dp[m][i]);
if(ans == INT_MAX)
ans = -1;
cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |