立命館プログラミング合宿2012 day1 問題G Sports Days (AOJ1090)

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1090）

制約条件

n≦100
1≦col[i]≦4
m≦2000
1≦ai,bi≦n
-1000≦ci≦1000
1≦k≦10
patternは1〜4からなる長さ10以下の文字列

方針

しおたさんの解説がわかりやすい。id:shioshiota:20120321

パターンマッチオートマトンをKMPで作り、
その状態で頂点を多重化したグラフでk-最短路を求めればよい。

負辺が含まれているので、ポテンシャルを求めて負辺を除去する。
ポテンシャルについては蟻本の費用流の解説のあたりにあったのでそこ参照。

グラフの途中に負閉路があったら-1を返す。

ソースコード

k-最短路とかはspaghetti sourceのだけど一部間違っているので修正。

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

//fixed
vi k_shortestPath(const Graph &g, int s, int t, int k,int *h) {
  int n=g.size();
  vi dist[n];
  priority_queue<Edge> Q; Q.push(Edge(-1, s, 0));
  while (!Q.empty()) {
    Edge e = Q.top(); Q.pop();
    if (dist[e.dst].size() >= k) continue;
    dist[e.dst].push_back(e.weight);
    fr(f, g[e.dst]) Q.push(Edge(f->src, f->dst, f->weight+e.weight+h[f->src]-h[f->dst]));
  }
  rep(i,dist[t].size())dist[t][i]+=h[t]-h[s];
  return dist[t];
}
int *buildFail(char *p) {
  int m = strlen(p);
  int *fail = new int[m+1];
  int j = fail[0] = -1;
  for (int i = 1; i <= m; ++i) {
    while (j >= 0 && p[j] != p[i-1]) j = fail[j];
    fail[i] = ++j;
  }
  return fail;
}

int n,col[100],m,a[1000],b[1000],c[1000],k;
char ptn[20];
int V,s,t,h[1111];
Graph G,rG;

bool v[1111],rv[1111];
void dfs(int c,const Graph &g,bool *v){
	v[c]=1;
	fr(i,g[c])if(!v[i->dst])dfs(i->dst,g,v);
}
bool calc_potential(){
	fill(h,h+V+1,0);
	rep(k,V)rep(i,V)if(v[i]&&rv[i])fr(e,G[i]){
		if(h[e->dst]>h[e->src]+e->weight){
			h[e->dst]=h[e->src]+e->weight;
			if(k==V-1)return 0;
		}
	}
	return 1;
}
inline void push(Graph &g,int src,int dst,int weight){
	g[src].pb(Edge(src,dst,weight));
}
bool make_graph(){
	int *fail=buildFail(ptn), len=strlen(ptn);
	G.clear(); rG.clear();
	V=n*(len+1)+1;
	s=0; t=V-1;
	while(s>=0&&ptn[s]-'0'!=col[0])s=fail[s];
	if(++s>=len)return 0;
	G.resize(V); rG.resize(V);
	
	vector<vector<pi> > e(n);
	rep(i,m)e[a[i]-1].pb(mp(b[i]-1,c[i]));
	
	rep(i,n)rep(j,len+1){
		fr(k,e[i]){
			int to=j;
			while(to>=0&&ptn[to]-'0'!=col[k->first])to=fail[to];
			if(++to>=len)continue;
			push(G,i*(len+1)+j,k->first*(len+1)+to,k->second);
			push(rG,k->first*(len+1)+to,i*(len+1)+j,0);
		}
	}
	rep(j,len){
		push(G,(n-1)*(len+1)+j,t,0);
		push(rG,t,(n-1)*(len+1)+j,0);
	}
	rep(i,V)v[i]=rv[i]=0;
	dfs(s,G,v); dfs(t,rG,rv);
	return v[t]&&rv[s];
}

int main(){
	while(cin>>n,n){
		rep(i,n)cin>>col[i];
		cin>>m;
		rep(i,m)cin>>a[i]>>b[i]>>c[i];
		cin>>k>>ptn;
		
		if(!make_graph()){
			cout<<"0 0"<<endl; continue;
		}
		if(!calc_potential()){
			cout<<-1<<endl; continue;
		}
		vi ans=k_shortestPath(G,s,t,k,h);
		int sum=0;
		rep(i,ans.size())sum+=ans[i];
		cout<<ans.size()<<" "<<sum<<endl;
	}
	return 0;
}