Submission #69380385

---

Source Code Expand

// 华风夏韵 洛水天依
// 天依宝宝可爱！> <

#include<bits/stdc++.h>

#define int long long
#define double long double
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rpe(i,a,b) for(int i=(a);i>=(b);--i)
#define repp(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define rpee(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define inf (int)(0x3f3f3f3f3f3f3f3f)
#define pii pair <int,int>
#define st first
#define nd second
#define mp make_pair
#define pb emplace_back
#define all(x) (x).begin(),(x).end()
#define mxele *max_element
#define mnele *min_element
#define gsum(l,r) accumulate((l),(r),0)
#define umap unordered_map
#define uset unordered_set
#define prque(a,b) priority_queue <a,vector<a>,b<a>>
#define popc __builtin_popcount
#define lowb lower_bound
#define uppb upper_bound

using namespace std;
bool memory_begin;

namespace fast_io{char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0,ny,precision=19;bool isEOF=0;unsigned long long pw10[20];il bool init_pw10(){pw10[0]=1ull;rep(i,1,19)pw10[i]=pw10[i-1]*10ull;return 1;}il char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}il int read(){int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc^EOF)nc==45&&(ny=-1);Bi=1;if(nc<0)return isEOF=1,nc;x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc^EOF)x=(x<<3)+(x<<1)+(nc^48),++Bi;return x*ny;}il void read(int &x){x=read();}il void read(char &x){while(nc=gc(),nc<33&&nc^EOF);nc<0&&(isEOF=1);x=nc;}il void read(pii&a){a.st=read(),a.nd=read();}il void read(double &x){pw10[0]||init_pw10();int a=read(),y=ny,b=(nc!='.')?0:read();x=(b?a+(double)b/pw10[Bi]*y:a);}il void read(string &s){s="";while(nc=gc(),nc<33&&nc^EOF);nc<0&&(isEOF=1);s+=nc;while(nc=gc(),nc>=33)s+=nc;}il signed read(char *s){char *t=s;while(nc=gc(),nc<33&&nc^EOF);nc<0&&(isEOF=1);*s++=nc;while(nc=gc(),nc>=33)*s++=nc;return s-t;}template <typename T,typename ... Args> il void read(T &x, Args &... y) {read(x);read(y...);}il void ot(){fwrite(sr,1,C+1,stdout);C=-1;}il void flush(){if(C>1<<22)ot();}il void pc(char c){sr[++C]=c;flush();}il void write(int x,char t='\0'){int y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);t=='\0'||(sr[++C]=t);flush();}il void write(char x,char t='\0'){sr[++C]=x,t=='\0'||(sr[++C]=t);flush();}il void write(pii a,char t='\0'){write(a.st,' '),write(a.nd,t);flush();}il void write(double x,char t='\0'){pw10[0]||init_pw10();write((int)x,'.'),write((int)((x-(int)x)*pw10[precision]),t);flush();}il void write(string s,char t='\0'){int l=s.size();rep(i,0,l-1)sr[++C]=s[i];t=='\0'||(sr[++C]=t);flush();}il void write(char *s,char t='\0'){int l=strlen(s);rep(i,0,l-1)sr[++C]=*s++;t=='\0'||(sr[++C]=t);flush();}template <typename T,typename ... Args> il void write(T x, Args ... y){write(x,' ');write(y...);}}
using fast_io::read,fast_io::write;
namespace _{template <typename T> il void r(T*a,int n){rep(i,1,n)read(a[i]);}template <typename T1,typename T2> il void r(T1 *a,T2 *b,int n){rep(i,1,n)read(a[i]),read(b[i]);}template <typename T1,typename T2,typename T3> il void r(T1 *a,T2 *b,T3 *c,int n){rep(i,1,n)read(a[i]),read(b[i]),read(c[i]);}template <typename T> il void r(T*a,int n,int m){rep(i,1,n)rep(j,1,m)read(a[i][j]);}template <typename T> il void r(vector<T>&a,int n){a.resize(n);rep(i,0,n-1)read(a[i]);}template <typename T> il void r(vector<T>*p,int m,bool op){int u,v;rep(i,1,m)read(u,v),p[u].pb(v),op||(p[v].pb(u),1);}template <typename T1,typename T2> il void r(vector<pair<T1,T2>>*p,int m,bool op){int u,v,w;rep(i,1,m)read(u,v,w),p[u].pb(v,w),op||(p[v].pb(u,w),1);}template <typename T> il void w(T*a,int n){rep(i,1,n-1)write(a[i],' ');n&&(write(a[n]),1),write('\n');}template <typename T> il void w(T*a,int n,int m){rep(i,1,n){rep(j,1,m-1)write(a[i][j],' ');m&&(write(a[i][m]),1),write('\n');}}template <typename T> il void w(vector<T>&a){rep(i,0,(int)a.size()-2)write(a[i],' ');!a.empty()&&(write(a.back()),1),write('\n');}}
#define is_debug 1
namespace dbg{template <typename T> il void arr(T*a,int n){if(!is_debug)return;rep(i,1,n-1)cerr<<a[i]<<' ';n&&(cerr<<a[n],1),cerr<<'\n';} template <typename T> il void arr(string s,T *a,int n){if(!is_debug)return;cerr<<s<<" : ";arr(a,n);}template <typename T> il void mat(T*a,int n,int m){if(!is_debug)return;rep(i,1,n){rep(j,1,m-1)cerr<<a[i][j]<<' ';m&&(cerr<<a[i][m],1),cerr<<'\n';}cerr<<'\n';} template <typename T> il void mat(string s,T *a,int n,int m){if(!is_debug)return;cerr<<s<<" :\n";mat(a,n,m);}template <typename T> il void vec(vector<T>a){if(!is_debug)return;rep(i,0,(int)a.size()-2)cerr<<a[i]<<' ';!a.empty()&&(cerr<<a.back(),1),cerr<<'\n';} template <typename T> il void vec(string s,vector <T> a){if(!is_debug)return;cerr<<s<<" : ";vec(a);}template <typename T> il void graV(vector<T>*p,int n){if(!is_debug)return;rep(u,1,n){cerr<<u<<" : ";rep(i,0,(int)p[u].size()-2)cerr<<p[u][i]<<' ';!p[u].empty()&&(cerr<<p[u].back(),1),cerr<<'\n';}cerr<<'\n';} template <typename T> il void graV(string s,vector <T> *p,int n){if(!is_debug)return;cerr<<s<<" :\n";graV(p,n);}template <typename T1,typename T2> il void graV(vector<pair<T1,T2>>*p,int n){if(!is_debug)return;rep(u,1,n){cerr<<u<<" : ";rep(i,0,(int)p[u].size()-2)cerr<<p[u][i].st<<','<<p[u][i].nd<<' ';!p[u].empty()&&(cerr<<p[u].back().st<<','<<p[u].back().nd,1),cerr<<'\n';}cerr<<'\n';} template <typename T1,typename T2> il void graV(string s,vector <pair<T1,T2>> *p,int n){if(!is_debug)return;cerr<<s<<" :\n";graV(p,n);}template <typename T> il void graE(vector<T>*p,int n,bool op){if(!is_debug)return;rep(u,1,n)for(auto v:p[u])(op||u<v)&&(cerr<<u<<' '<<v<<'\n',1);cerr<<'\n';} template <typename T> il void graE(string s,vector <T> *p,int n,bool op){if(!is_debug)return;cerr<<s<<" :\n";graE(p,n,op);}template <typename T1,typename T2> il void graE(vector<pair<T1,T2>>*p,int n,bool op){if(!is_debug)return;rep(u,1,n)for(auto [v,w]:p[u])(op||u<v)&&(cerr<<u<<' '<<v<<' '<<w<<'\n',1);cerr<<'\n';} template <typename T1,typename T2> il void graE(string s,vector <pair<T1,T2>> *p,int n,bool op){if(!is_debug)return;cerr<<s<<" :\n";graE(p,n,op);}}

const int N=50+5,M=6e5+5,V=6e5+5,mod=998244353;
const int dx[10]={0,0,1,0,-1,1,1,-1,-1},dy[10]={0,1,0,-1,0,1,-1,1,-1};
const double eps=1e-9;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
il double gtime(){return clock()*1e3/CLOCKS_PER_SEC;}
template <typename T> il void clr(T &x){T().swap(x);}
template <typename T1,typename T2> il T1& add(T1 &a,T2 b){a+=b,a>=0?(a>=mod&&(a-=mod)):(a<-mod?a+=mod<<1:a+=mod);return a;}
template <typename T1,typename T2> il T1& chmax(T1 &a,T2 b){return a<b&&(a=b,1),a;}
template <typename T1,typename T2> il T1& chmin(T1 &a,T2 b){return a>b&&(a=b,1),a;}
il long long mod_(const long long &x){unsigned long long ux=(x>=0?x:-x),r=ux-(__uint128_t(ux)*9920937979283557439ull>>93)*998244353; return x>=0?r:mod-r;}
//il long long mod_(const long long &x){unsigned long long ux=(x>=0?x:-x),r=ux-(__uint128_t(ux)*9903520244958400484ull>>93)*1000000007; return x>=0?r:mod-r;}
//il long long mod_(const long long &x){return x<0?x%mod+mod:x%mod;}

#define multiple_test 0
int __T=1;

const int L=2000+5;
int n;
struct {string s; int c;} a[N];
vector <pii> p[L];
map <string,int> to;

namespace dij
{
	int dis[L],n;
	bitset <L> vis;
	
	il void solve(int _n,int s=1)
	{
		n=_n;
		prque(pii,greater) q; rep(i,0,n+1) dis[i]=inf;
		q.emplace(0,s),dis[s]=0;
		int u;
		while(!q.empty())
		{
			u=q.top().nd,q.pop();
			if(vis[u]) continue;
			vis[u]=1;
			for(auto [v,w]:p[u]) dis[v]>dis[u]+w && (dis[v]=dis[u]+w,q.emplace(dis[v],v),1);
		}
		
//		dbg::arr("dis",dis,n);
	}
}

il void solve(int __Ti)
{
//    double time_begin=gtime();
	
	read(n); rep(i,1,n) read(a[i].s),read(a[i].c);
	
	string tmp; int tot=1;
	rep(i,1,n) to.count(a[i].s) || (to[a[i].s]=++tot);
	rep(i,1,n)
	{
		tmp="";
		rep(j,0,(int)a[i].s.size()-2) tmp+=a[i].s[j],to.count(tmp) || (to[tmp]=++tot);
		tmp="";
		rpe(j,(int)a[i].s.size()-1,1) tmp=a[i].s[j]+tmp,to.count(tmp) || (to[tmp]=++tot);
	}
	
//	cerr<<"to : \n";
//	for(auto [s,id]:to) cerr<<"  "<<id<<" : "<<s<<'\n';
	
	string s,t; bool swap_fl=0; int sl,tl;
	rep(i,1,n) p[1].pb(to[a[i].s],a[i].c);
	for(auto [_s,id]:to)
	{
		s=_s;
		if(s==(tmp=s,reverse(all(tmp)),tmp)) {p[id].pb(tot+1,0); continue;}
		
		rep(i,1,n)
		{
			t=a[i].s;
			s.size()<t.size() && (swap_fl=1,swap(s,t),1);
			reverse(all(t));
			
//			cerr<<"checking... "<<s<<' '<<t<<" | id = "<<id<<" , i = "<<i<<'\n';
			
			if(s==t) p[id].pb(tot+1,a[i].c);//,fprintf(stderr,"case 1 s==t : adde %lld ---> %lld (%lld)\n",id,tot+1,a[i].c);
			else
			{
				sl=s.size(),tl=t.size();
				if(s.find(t)==0) p[id].pb(to[s.substr(tl,sl-tl)],a[i].c);//,fprintf(stderr,"case 2 t is s.pre : adde %lld ---> %lld (%lld)\n",id,to[s.substr(tl,sl-tl)],a[i].c);
				if(s.rfind(t)==sl-tl) p[id].pb(to[s.substr(0,sl-tl)],a[i].c);//,fprintf(stderr,"case 3 t is s.suf : adde %lld ---> %lld (%lld)\n",id,to[s.substr(0,sl-tl)],a[i].c);
			}
			
			reverse(all(t));
			swap_fl && (swap(s,t),swap_fl=0);
		}
	}
	
//	dbg::graE("p",p,tot+1,true);
	
	dij::solve(tot+1);
	write(dij::dis[tot+1]>=inf-712 ? -1ll : dij::dis[tot+1]);
	
//    cerr<<"task "<<__Ti<<" : time = "<<gtime()-time_begin<<" ms\n";
}

il void init()
{
	
}

bool memory_end;
signed main()
{
//    freopen(".in","r",stdin),freopen(".out","w",stdout);
//    ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
	fprintf(stderr,"memory = %.3lf MB\n\n",abs(&memory_end-&memory_begin)/1048576.);
	init(); multiple_test&&(read(__T),1);
	rep(__Ti,1,__T) solve(__Ti);
//    int __Ti=0; while(read(n),!fast_io::isEOF) solve(++__Ti);
	fprintf(stderr,"\ntime = %.3Lf ms\n",gtime());
	return fast_io::ot(),0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve(long long int)’:
Main.cpp:124:46: warning: comparison of integer expressions of different signedness: ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} and ‘long long int’ [-Wsign-compare]
  124 |                                 if(s.rfind(t)==sl-tl) p[id].pb(to[s.substr(0,sl-tl)],a[i].c);//,fprintf(stderr,"case 3 t is s.suf : adde %lld ---> %lld (%lld)\n",id,to[s.substr(0,sl-tl)],a[i].c);
      |                                    ~~~~~~~~~~^~~~~~~
Main.cpp:85:19: warning: unused parameter ‘__Ti’ [-Wunused-parameter]
   85 | il void solve(int __Ti)
      |                   ^

Judge Result