AOJ 1090-Sports Days

問題概要

日本語なので略

解法

まず，KMPパターンマッチングを用いてグラフを単純化する．
スタートとゴールから辿り付ける範囲に負の閉路がある場合は解が-1．
そうで無い場合はベルマンフォードでポテンシャルを求めて，k番目までの最短路を求めるようなダイクストラを行なう．

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;

typedef long long int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

const int INF=999999999;

struct Edge{
  int src,dst,cost;
};
typedef vector<Edge> Node;
typedef vector<Node> Graph;

void add_edge(Graph &G,int src,int dst,int cost){
  G[src].push_back((Edge){src,dst,cost});
}

Graph reverseGraph(const Graph &G){
  Graph ret(G.size());
  REP(i,G.size()){
    REP(j,G[i].size()){
      const Edge &e=G[i][j];
      add_edge(ret,e.dst,e.src,e.cost);
    }
  }
  return ret;
}

int n,m,k;
string pattern;
int col[100];

Graph in;

bool input(){
  cin>>n;
  if(!n)return false;
  REP(i,n)cin>>col[i];
  in=Graph(n);
  cin>>m;
  REP(i,m){
    int a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    add_edge(in,a,b,c);
  }
  cin>>k>>pattern;
  return true;
}

//パターンを考慮したグラフを生成
Graph solvePattern(){
  int p=pattern.size();
  Graph G(n*p+1); //拡張グラフ
  REP(i,n){
    REP(j,p){
      REP(k,in[i].size()){
        Edge &e=in[i][k];
        if(pattern[j]==col[e.dst]+'0'){
          if(j+1<p)add_edge(G,i*p+j,e.dst*p+j+1,e.cost);
        }else{          string tmp=pattern.substr(0,j)+(char)(col[e.dst]+'0');
          //一番マッチングするものを選択
          RREP(s,tmp.size()){
            if(tmp.substr(tmp.size()-s)==pattern.substr(0,s)){
              if(s<p)add_edge(G,i*p+j,e.dst*p+s,e.cost);
              break;
            }
          }
        }
      }
    }
  }
  // 終点を固定する
  REP(j,p){
    add_edge(G,p*(n-1)+j,n*p,0);
  }
  return G;
}

// ある頂点から行ける頂点を求める
vector<bool> canGo(const Graph &G,int src){
  vector<bool> ac(G.size());
  ac[src]=true;
  queue<int> que;
  que.push(src);
  while(!que.empty()){
    int now=que.front();que.pop();
    REP(i,G[now].size()){
      const Edge &e=G[now][i];
      if(ac[e.dst]==false){
        ac[e.dst]=true;
        que.push(e.dst);
      }
    }
  }
  return ac;
}

// 不要な辺を消去する
Graph removeEdge(const Graph &G,vector<bool> use){
  Graph ret(G.size());
  REP(i,G.size()){
    REP(j,G[i].size()){
      const Edge &e=G[i][j];
      if(use[e.src]&&use[e.dst]){
        add_edge(ret,e.src,e.dst,e.cost);
      }
    }
  }
  return ret;
}

//負の辺を含む最短経路
vector<int> shortestPath(const Graph &G,int s){
  vector<int> dist(G.size(),INF);
  dist[s]=0;
  int count=0;
  bool update;
  do{
    update=false;
    if(count++>(int)G.size()+2)return vector<int>();
    REP(i,G.size()){
      if(dist[i]==INF)continue;
      REP(j,G[i].size()){
        const Edge &e=G[i][j];
        if(dist[e.dst]>dist[e.src]+e.cost){
          dist[e.dst]=dist[e.src]+e.cost;
          update=true;
        }
      }
    }
  }while(update);
  return dist;
}

void add_multiset(multiset<int> &s,int number){
  s.insert(number);
  if((int)s.size()>k){
    multiset<int>::iterator it=s.end();
    it--;
    s.erase(it);
  }
}

int main(){
  while(input()){
    Graph G=solvePattern();

    int start=0;
    if(col[0]==pattern[0]-'0'){
      start=1;
      if(pattern.size()==1){
        cout<<"0 0"<<endl; //スタートに立てない
        continue;
      }
    }
    
    // 終点から行ける点を求める
    vector<bool> fromStart=canGo(G,start);
    vector<bool> fromGoal=canGo(reverseGraph(G),G.size()-1);
    vector<bool> route(G.size());
    REP(i,G.size()){
      route[i]=(fromStart[i]&&fromGoal[i]);
    }
    G=removeEdge(G,route);

    // ベルマンフォードを用いてポテンシャルを求める
    vector<int> pot=shortestPath(G,start);
    if(pot.empty()){
      //負の閉路有り
      cout<<-1<<endl;
    }else{
      vector<multiset<int> > d(G.size());
      vector<int> &h=pot;
      REP(i,G.size()){
        REP(v,k)d[i].insert(INF);
      }
      add_multiset(d[0],start);
      
      typedef pair<int,int> P;
      priority_queue<P,vector<P>,greater<P> > que;
      que.push(P(0,start));
      
      while(!que.empty()){
        P now=que.top();que.pop();
        if(now.first>*d[now.second].rbegin())continue;
        REP(i,G[now.second].size()){
          Edge &e=G[now.second][i];
          if(*d[e.dst].rbegin()>now.first+e.cost+h[e.src]-h[e.dst]){
            add_multiset(d[e.dst],now.first+e.cost+h[e.src]-h[e.dst]);
            que.push(P(now.first+e.cost+h[e.src]-h[e.dst],e.dst));
          }
        }
      }
      int count=0,ans=0;
      FOR(it,d[G.size()-1]){
        if(*it!=INF){
          count++;
          ans+=*it+h[G.size()-1]-h[start];
        }
      }
      cout<<count<<" "<<ans<<endl;
    }
  }
}