题意：反转一些字符串使得其按照字典序排列，输出最小的花费。
思路：将相邻两个字符串如果满足字典序要求就连边，从起点跑最短路 。也可以用dp来解决。
错误原因：这道题如果跑最短路不能加双向边，因为加入后又0花费的边，则最短路有可能往回走，不跟预期不一样了。
ac代码：（最短路）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
#include<unordered_map>
#define mod (1000000007)
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 5;
const ll inf = 1e16;
struct node{int v,nxt;ll w;
}side[maxn<<2];
int head[maxn],cnt=0,n,st=0,vis[maxn];
ll dis[maxn],w[maxn];
void add(int x,int y,ll w){side[cnt].v=y;side[cnt].w=w;side[cnt].nxt=head[x];head[x]=cnt++;
}
char las[maxn],lasn[maxn],now[maxn],nown[maxn];
struct nod{int v;ll w;nod(){}nod(int vv,ll ww):v(vv),w(ww){}friend bool operator<(nod a,nod b){return a.w>b.w;}
};
void dijkstra(int st){for(int i=0;i<2*n+10;i++) dis[i]=inf,vis[i]=0;priority_queue<nod> q;dis[st]=0;q.push(nod(st,0));while(!q.empty()){nod nn=q.top();q.pop();if(vis[nn.v])continue;vis[nn.v]=1;for(int i=head[nn.v];i!=-1;i=side[i].nxt){int ty=side[i].v;if(dis[ty]>dis[nn.v]+side[i].w){dis[ty]=dis[nn.v]+side[i].w;q.push(nod(ty,dis[ty]));}}}
}
int main() {scanf("%d",&n);for(int i=0;i<2*n+5;i++)head[i]=-1;for(int i=1;i<=n;i++)scanf("%lld",&w[i]);las[0]=0;lasn[0]=0;for(int i=1;i<=n;i++){scanf("%s",now);int le=strlen(now);strcpy(nown,now);reverse(nown,nown+le);if(strcmp(las,now)<=0){//不能加双向边？？？ add(i-1,i,0);}if(strcmp(las,nown)<=0){add(i-1,i+n,w[i]);}if(strcmp(lasn,now)<=0){add(i==1?0:(i-1+n),i,0);}if(strcmp(lasn,nown)<=0){add((i==1)?0:(i-1+n),i+n,w[i]);}strcpy(las,now);strcpy(lasn,nown);}dijkstra(st);ll res=min(dis[n],dis[n+n]);printf("%lld\n",res==inf?-1:res);return 0 ;
}
/*
3
1 3 1
aa
ba
ac
*/ ac代码：（dp）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
#define mod (1000000007)
using namespace std;
typedef long long ll;int n;
int c[101100];
string ss[101010];
ll dp[101010][2];
int main()
{memset(dp,0x3f3f3f3f,sizeof(dp));scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&c[i]);for(int i=0;i<n;i++)cin>>ss[i];dp[0][0]=0;dp[0][1]=c[0];for(int i=1;i<n;i++){string s1=ss[i],s2=ss[i-1],s3=ss[i],s4=ss[i-1];reverse(s4.begin(),s4.end());reverse(s3.begin(),s3.end());if(s1>=s2)dp[i][0]=min(dp[i][0],dp[i-1][0]);if(s1>s4)dp[i][0]=min(dp[i][0],dp[i-1][1]);if(s3>s2) dp[i][1]=min(dp[i][1],dp[i-1][0]+c[i]);if(s3>s4)dp[i][1]=min(dp[i][1],dp[i-1][1]+c[i]);if(dp[i][1]==4557430888798830399&&dp[i][0]==4557430888798830399)break;}ll ans=min(dp[n-1][0],dp[n-1][1]);if(ans==4557430888798830399)ans=-1;cout<<ans<<endl;return 0;
}