WA了14个点,做法是正反串建trie,暴力最短路...
#include<bits/stdc++.h>
#define fi first
#define se second
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pi pair<int,int>
#define fi first
#define se second
#define pb push_back
#define IT iterator
#define vi vector<int>
#define vl vector<ll>
#define SZ(a) ((int)a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N=55,T=1010,size=1<<20,mod=998244353;
const ll inf=1e18;
template<class o> void qr(o &x) {
char c=gc; x=0; int f=1;
while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
while(isdigit(c)) x=x*10+c-'0',c=gc;
x*=f;
}
template<class o> void qw(o x) {
if(x/10) qw(x/10);
putchar(x%10+'0');
}
template<class o> void pr1(o x) {
if(x<0)x=-x,putchar('-');
qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
if(x<0)x=-x,putchar('-');
qw(x); puts("");
}
int n;
char s[N];
struct AC {
int trie[T][26],fail[T],tot=1,ed[T];
void ins(char *s,int x) {
int p=1;
for(int i=1;s[i];i++) {
int c=s[i]-'a';
if(!trie[p][c]) trie[p][c]=++tot;
p=trie[p][c];
}
if(ed[p]) ed[p]=min(ed[p],x);
else ed[p]=x;
}
} a,b;
ll f[T][T],ans=inf;
bool vis[T][T];
struct rec {
int x,y;ll z;
rec(int a=1,int b=1,ll c=0) {x=a; y=b; z=c;}
bool operator<(rec b) const {return z>b.z;}
} ;
priority_queue<rec> q;
void add(int x,int y,ll z) {
if(f[x][y]>z)
f[x][y]=z,q.push(rec(x,y,z));
}
void solve() {
memset(f,63,sizeof f); add(1,1,0);
while(q.size()) {
int x=q.top().x,y=q.top().y; q.pop();
if(vis[x][y]) continue;
vis[x][y]=1;
for(int c=0;c<26;c++) {
int tx=a.trie[x][c],ty=b.trie[y][c];
if(tx&&ty&&!vis[tx][ty]) {
add(tx,ty,f[x][y]);
ll u=a.ed[tx],v=b.ed[ty];
if(u) add(1,ty,u+f[x][y]);
if(v) add(tx,1,f[x][y]+v);
if(u&&v) ans=min(ans,f[x][y]+u+v);
}
}
}
if(ans==inf) puts("-1");
else pr2(ans/2);
}
int main() {
qr(n);
for(int i=1,x;i<=n;i++) {
scanf("%s",s+1); qr(x);
a.ins(s,x);
int len=strlen(s+1);
reverse(s+1,s+len+1);
b.ins(s,x);
}
solve();
return 0;
}