最短路做法的话 关键是怎么去建边
我们假设从一个虚拟点出发(顶点编号0),每个字符串正串顶点编号是2i-1,反串顶点编号是2i
如果前面一个字符串<后面字符串,建边。如果不翻转,边权重为0,翻转权重是 c[i]
然后dijkstra算法
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int N=4e5+10;
int c[N];
vector<PII> e[N];
priority_queue<PII,vector<PII>,greater<PII>> q;
bool vis[N];
int n;
vector<int> dist(N+1,9e18);
string rv(string s)
{
string str="";
for(int i=s.size()-1;i>=0;i--)str+=s[i];
return str;
}
void dijkstra()
{
dist[0]=0;
q.push({0,0});
while(q.size())
{
int u=q.top().second;
q.pop();
if(vis[u])continue;
vis[u]=true;
for(auto xx:e[u])
{
int v=xx.first,w=xx.second;
if(dist[u]+w<dist[v])
{
dist[v]=dist[u]+w;
q.push({dist[v],v});
}
}
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>c[i];
string pre1,pre2;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
if(i==1)
{
e[0].push_back({1,0});
e[0].push_back({2,c[1]});
pre1=s,pre2=rv(s);
}
else
{
int id1=(i-2)*2+1,id2=(i-1)*2;
string cur1=s,cur2=rv(s);
if(pre1<=cur1)e[id1].push_back({(i-1)*2+1,0});
if(pre1<=cur2)e[id1].push_back({(i-1)*2+2,c[i]});
if(pre2<=cur1)e[id2].push_back({(i-1)*2+1,0});
if(pre2<=cur2)e[id2].push_back({(i-1)*2+2,c[i]});
pre1=cur1,pre2=cur2;
}
}
dijkstra();
int ans=min(dist[n*2],dist[n*2-1]);
if(ans>=9e18)puts("-1");
else cout<<ans<<endl;
return 0;
}