Language: C++

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>




using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);




#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))




typedef int Weight;
struct Edge {
&#160; int src;
&#160; int dest;
&#160; Weight weight;
&#160; Edge(int src, int dest, Weight weight) : src(src), dest(dest), weight(weight) {;}
&#160; bool operator<(const Edge &rhs) const {
&#160; &#160; return weight > rhs.weight;
&#160; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;




void PrintMatrix(const Matrix &matrix) {
&#160; for (int y = 0; y < (int)matrix.size(); y++) {
&#160; &#160; for (int x = 0; x < (int)matrix[y].size(); x++) {
&#160; &#160; &#160; printf("%d ", matrix[y][x]);
&#160; &#160; }
&#160; &#160; puts("");
&#160; }
}




bool end[1100];
static const Weight INF = 2000000000LL;
Weight BellmanFord(const Graph &g, Array &dist) {
&#160; const int n = g.size();
&#160; dist = Array(n, 0x0f0f0f0f);
&#160; dist[0] = 0;
&#160; REP(iter, n) {
&#160; &#160; bool e = true;
&#160; &#160; REP(i, n) {
&#160; &#160; &#160; REP(j, g[i].size()) {
&#160; &#160; &#160; &#160; int to = g[i][j].dest;
&#160; &#160; &#160; &#160; Weight ncost = dist[i] + g[i][j].weight;
&#160; &#160; &#160; &#160; if (dist[to] > ncost) {
&#160; &#160; &#160; &#160; &#160; dist[to] = ncost;
&#160; &#160; &#160; &#160; &#160; e = false;
&#160; &#160; &#160; &#160; }
&#160; &#160; &#160; }
&#160; &#160; }
&#160; &#160; if (e) { return 0; }
&#160; }
&#160; return -INF;
}




int n, m, k, len;
int color[110];
char ban[1000];
int memo[20][20];




int OneMove(int pattern, int c) {
&#160; if (ban[pattern] == c) { return pattern + 1; }
&#160; if (memo[pattern][c] != -1) { return memo[pattern][c]; }
&#160; deque<int> now;
&#160; REP(i, pattern) { now.push_back(ban[i]); }
&#160; now.push_back(c);
&#160; while (!now.empty()) {
&#160; &#160; now.pop_front();
&#160; &#160; REP(i, now.size()) {
&#160; &#160; &#160; if (now[i] != ban[i]) { goto next; }
&#160; &#160; }
&#160; &#160; break;
next:;
&#160; }
&#160; return memo[pattern][c] = now.size();
}




Graph Expand(Graph g) {
&#160; MEMSET(memo, -1);
&#160; vector<bool> visit(n * len, false);
&#160; queue<pair<int, int> > que;
&#160; int first = color[0] == ban[0] ? 1 : 0;
&#160; que.push(make_pair(0, first));
&#160; Graph ret(n * len);
&#160; if (len == first) { return ret; }
&#160; while (!que.empty()) {
&#160; &#160; int from = que.front().first;
&#160; &#160; int pattern = que.front().second;
&#160; &#160; que.pop();
&#160; &#160; if (visit[from * len + pattern]) { continue; }
&#160; &#160; visit[from * len + pattern] = true;
&#160; &#160; FORIT(it, g[from]) {
&#160; &#160; &#160; int to = it->dest;
&#160; &#160; &#160; int c = color[to];
&#160; &#160; &#160; int npattern = OneMove(pattern, c);
&#160; &#160; &#160; if (npattern == len) { continue; }
&#160; &#160; &#160; ret[from * len + pattern].push_back(Edge(from * len + pattern, to * len + npattern, it->weight));
&#160; &#160; &#160; que.push(make_pair(to, npattern));
&#160; &#160; }
&#160; }
&#160; return ret;
}




Graph revG(Graph g) {
&#160; Graph ret(g.size());
&#160; REP(i, g.size()) {
&#160; &#160; FORIT(it, g[i]) {
&#160; &#160; &#160; ret[it->dest].push_back(Edge(it->dest, it->src, it->weight));
&#160; &#160; }
&#160; }
&#160; return ret;
}




void dfs(const Graph &g, int from, vector<bool> &visit) {
&#160; if (visit[from]) { return; }
&#160; visit[from] = true;
&#160; FORIT(it, g[from]) {
&#160; &#160; dfs(g, it->dest, visit);
&#160; }
}




Graph Erase(Graph g) {
&#160; MEMSET(end, false);
&#160; vector<bool> visit1(1010, 0);
&#160; vector<bool> visit2(1010, 0);
&#160; Graph rev = revG(g);
&#160; dfs(g, color[0] == ban[0], visit1);
&#160; if (len == 1 && color[0] == ban[0]) { visit1[1] = false; }
&#160; REP(i, len) { dfs(rev, (n - 1) * len + i, visit2); }
&#160; int m = 0;
&#160; map<int, int> mapto;
&#160; REP(i, n * len) {
&#160; &#160; if (!visit1[i] || !visit2[i]) { continue; }
&#160; &#160; if (i >= (n - 1) * len) { end[m] = true; }
&#160; &#160; mapto[i] = m++;
&#160; }
&#160; Graph ret(m);
&#160; REP(i, n * len) {
&#160; &#160; if (!mapto.count(i)) { continue; }
&#160; &#160; int from = mapto[i];
&#160; &#160; FORIT(it, g[i]) {
&#160; &#160; &#160; if (!mapto.count(it->dest)) { continue; }
&#160; &#160; &#160; int to = mapto[it->dest];
&#160; &#160; &#160; ret[from].push_back(Edge(from, to, it->weight));
&#160; &#160; }
&#160; }
&#160; return ret;
}




vector<int> dists[1010];
pair<int, int> calc(const Graph &g) {
&#160; if (g.size() == 0) { return make_pair(0, 0); }
&#160; Array dist;
&#160; int v = BellmanFord(g, dist);
&#160; if (v == -INF) { return make_pair(-1, -1); }
&#160; priority_queue<Edge> que;
&#160; que.push(Edge(0, 0, 0));
&#160; REP(i, 1010) { dists[i].clear(); }
&#160; vector<int> ans;
&#160; while (!que.empty()) {
&#160; &#160; Edge e = que.top();
&#160; &#160; que.pop();
&#160; &#160; int from = e.dest;
&#160; &#160; if ((int)dists[from].size() == k) { continue; }
&#160; &#160; dists[from].push_back(e.weight);
&#160; &#160; if (end[from]) { ans.push_back(e.weight + dist[from]); }
&#160; &#160; FORIT(it, g[from]) {
&#160; &#160; &#160; int to = it->dest;
&#160; &#160; &#160; int ncost = it->weight + e.weight + (dist[from] - dist[to]);
&#160; &#160; &#160; que.push(Edge(from, to, ncost));
&#160; &#160; }
&#160; }
&#160; pair<int, int> ret = make_pair(0, 0);
&#160; sort(ans.begin(), ans.end());
&#160; ret.first = min(k, (int)ans.size());
&#160; REP(i, ret.first) { ret.second += ans[i]; }
&#160; return ret;
}




int main() {
&#160; while (scanf("%d", &n), n) {
&#160; &#160; REP(i, n) { scanf("%d", &color[i]); }
&#160; &#160; scanf("%d", &m);
&#160; &#160; Graph g(n);
&#160; &#160; REP(i, m) {
&#160; &#160; &#160; int f, t, c;
&#160; &#160; &#160; scanf("%d %d %d", &f, &t, &c);
&#160; &#160; &#160; f--; t--;
&#160; &#160; &#160; g[f].push_back(Edge(f, t, c));
&#160; &#160; }
&#160; &#160; scanf("%d", &k);
&#160; &#160; scanf("%s", ban);
&#160; &#160; len = strlen(ban);
&#160; &#160; REP(i, len) { ban[i] -= '0'; }
&#160; &#160; g = Expand(g);
&#160; &#160; g = Erase(g);
&#160; &#160; pair<int, int> ans = calc(g);
&#160; &#160; if (ans.first == -1) {
&#160; &#160; &#160; puts("-1");
&#160; &#160; } else {
&#160; &#160; &#160; printf("%d %d\n", ans.first, ans.second);
&#160; &#160; }
&#160; }
}

Compiler output:
a.cc:37:2: error: stray '#' in program
   37 | &#160; int src;
      |  ^
a.cc:38:2: error: stray '#' in program
   38 | &#160; int dest;
      |  ^
a.cc:39:2: error: stray '#' in program
   39 | &#160; Weight weight;
      |  ^
a.cc:40:2: error: stray '#' in program
   40 | &#160; Edge(int src, int dest, Weight weight) : src(src), dest(dest), weight(weight) {;}
      |  ^
a.cc:41:2: error: stray '#' in program
   41 | &#160; bool operator<(const Edge &rhs) const {
      |  ^
a.cc:42:2: error: stray '#' in program
   42 | &#160; &#160; return weight > rhs.weight;
      |  ^
a.cc:42:9: error: stray '#' in program
   42 | &#160; &#160; return weight > rhs.weight;
      |         ^
a.cc:43:2: error: stray '#' in program
   43 | &#160; }
      |  ^
a.cc:54:2: error: stray '#' in program
   54 | &#160; for (int y = 0; y < (int)matrix.size(); y++) {
      |  ^
a.cc:55:2: error: stray '#' in program
   55 | &#160; &#160; for (int x = 0; x < (int)matrix[y].size(); x++) {
      |  ^
a.cc:55:9: error: stray '#' in program
   55 | &#160; &#160; for (int x = 0; x < (int)matrix[y].size(); x++) {
      |         ^
a.cc:56:2: error: stray '#' in program
   56 | &#160; &#160; &#160; printf("%d ", matrix[y][x]);
      |  ^
a.cc:56:9: error: stray '#' in program
   56 | &#160; &#160; &#160; printf("%d ", matrix[y][x]);
      |         ^
a.cc:56:16: error: stray '#' in program
   56 | &#160; &#160; &#160; printf("%d ", matrix[y][x]);
      |                ^
a.cc:57:2: error: stray '#' in program
   57 | &#160; &#160; }
      |  ^
a.cc:57:9: error: stray '#' in program
   57 | &#160; &#160; }
      |         ^
a.cc:58:2: error: stray '#' in program
   58 | &#160; &#160; puts("");
      |  ^
a.cc:58:9: error: stray '#' in program
   58 | &#160; &#160; puts("");
      |         ^
a.cc:59:2: error: stray '#' in program
   59 | &#160; }
      |  ^
a.cc:68:2: error: stray '#' in program
   68 | &#160; const int n = g.size();
      |  ^
a.cc:69:2: error: stray '#' in program
   69 | &#160; dist = Array(n, 0x0f0f0f0f);
      |  ^
a.cc:70:2: error: stray '#' in program
   70 | &#160; dist[0] = 0;
      |  ^
a.cc:71:2: error: stray '#' in program
   71 | &#160; REP(iter, n) {
      |  ^
a.cc:72:2: error: stray '#' in program
   72 | &#160; &#160; bool e = true;
      |  ^
a.cc:72:9: error: stray '#' in program
   72 | &#160; &#160; bool e = true;
      |         ^
a.cc:73:2: error: stray '#' in program
   73 | &#160; &#160; REP(i, n) {
      |  ^
a.cc:73:9: error: stray '#' in program
   73 | &#160; &#160; REP(i, n) {
      |         ^
a.cc:74:2: error: stray '#' in program
   74 | &#160; &#160; &#160; REP(j, g[i].size()) {
      |  ^
a.cc:74:9: error: stray '#' in program
   74 | &#160; &#160; &#160; REP(j, g[i].size()) {
      |         ^
a.cc:74:16: error: stray '#' in program
   74 | &#160; &#160; &#160; REP(j, g[i].size()) {
      |                ^
a.cc:75:2: error: stray '#' in program
   75 | &#160; &#160; &#160; &#160; int to = g[i][j].dest;
      |  ^
a.cc:75:9: error: stray '#' in program
   75 | &#160; &#160; &#160; &#160; int to = g[i][j].dest;
      |         ^
a.cc:75:16: error: stray '#' in program
   75 | &#160; &#160; &#160; &#160; int to = g[i][j].dest;
      |                ^
a.cc:75:23: error: stray '#' in program
   75 | &#160; &#160; &#160; &#160; int to = g[i][j].dest;
      |                       ^
a.cc:76:2: error: stray '#' in program
   76 | &#160; &#160; &#160; &#160; Weight ncost = dist[i] + g[i][j].weight;
      |  ^
a.cc:76:9: error: stray '#' in program
   76 | &#160; &#160; &#160; &#160; Weight ncost = dist[i] + g[i][j].weight;
      |         ^
a.cc:76:16: error: stray '#' in program
   76 | &#160; &#160; &#160; &#160; Weight ncost = dist[i] + g[i][j].weight;
      |                ^
a.cc:76:23: error: stray '#' in program
   76 | &#160; &#160; &#160; &#160; Weight ncost = dist[i] + g[i][j].weight;
      |                       ^
a.cc:77:2: error: stray '#' in program
   77 | &#160; &#160; &#160; &#160; if (dist[to] > ncost) {
      |  ^
a.cc:77:9: error: stray '#' in program
   77 | &#160; &#160; &#160; &#160; if (dist[to] > ncost) {
      |         ^
a.cc:77:16: error: stray '#' in program
   77 | &#160; &#160; &#160; &#160; if (dist[to] > ncost) {
      |                ^
a.cc:77:23: error: stray '#' in program
   77 | &#160; &#160; &#160; &#160; if (dist[to] > ncost) {
      |                       ^
a.cc:78:2: error: stray '#' in program
   78 | &#160; &#160; &#160; &#160; &#160; dist[to] = ncost;
      |  ^
a.cc:78:9: error: stray '#' in program
   78 | &#160; &#160; &#160; &#160; &#160; dist[to] = ncost;
      |         ^
a.cc:78:16: error: stray '#' in program
   78 | &#160; &#160; &#160; &#160; &#160; dist[to] = ncost;
      |                ^
a.cc:78:23: error: stray '#' in program
   78 | &#160; &#160; &#160; &#160; &#160; dist[to] = ncost;
      |                       ^
a.cc:78:30: error: stray '#' in program
   78 | &#160; &#160; &#160; &#160; &#160; dist[to] = ncost;
      |                              ^
a.cc:79:2: error: stray '#' in program
   79 | &#160; &#160; &#160; &#160; &#160; e = false;
      |  ^
a.cc:79:9: error: stray '#' in program
   79 | &#160; &#160; &#160; &#160; &#160; e = false;
      |         ^
a.cc:79:16: error: stray '#' in program
   79 | &#160; &#160; &#160; &#160; &#160; e = false;
      |                ^
a.cc:79:23: error: stray '#' in program
   79 | &#160; &#160; &#160; &#160; &#160; e = false;
      |                       ^
a.cc:79:30: error: stray '#' in program
   79 | &#160; &#160; &#160; &#160; &#160; e = false;
      |                              ^
a.cc:80:2: error: stray '#' in program
   80 | &#160; &#160; &#160; &#160; }
      |  ^
a.cc:80:9: error: stray '#' in program
   80 | &#160; &#160; &#160; &#160; }
      |         ^
a.cc:80:16: error: stray '#' in program
   80 | &#160; &#160; &#160; &#160; }
      |                ^
a.cc:80:23: error: stray '#' in program
   80 | &#160; &#160; &#160; &#160; }
      |                       ^
a.cc:81:2: error: stray '#' in program
   81 | &#160; &#160; &#160; }
      |  ^
a.cc:81:9: error: stray '#' in program
   81 | &#160; &#160; &#160; }
      |         ^
a.cc:81:16: error: stray '#' in program
   81 | &#160; &#160; &#160; }
      |                ^
a.cc:82:2: error: stray '#' in program
   82 | &#160; &#160; }
      |  ^
a.cc:82:9: error: stray '#' in program
   82 | &#160; &#160; }
      |         ^
a.cc:83:2: error: stray '#' in program
   83 | &#160; &#160; if (e) { return 0; }
      |  ^
a.cc:83:9: error: stray '#' in program
   83 | &#160; &#160; if (e) { return 0; }
      |         ^
a.cc:84:2: error: stray '#' in program
   84 | &#160; }
      |  ^
a.cc:85:2: error: stray '#' in program
   85 | &#160; return -INF;
      |  ^
a.cc:100:2: error: stray '#' in program
  100 | &#160; if (ban[pattern] == c) { return pattern + 1; }
      |  ^
a.cc:101:2: error: stray '#' in program
  101 | &#160; if (memo[pattern][c] != -1) { return memo[pattern][c]; }
      |  ^
a.cc:102:2: error: stray '#' in program
  102 | &#160; deque<int> now;
      |  ^
a.cc:103:2: error: stray '#' in program
  103 | &#160; REP(i, pattern) { now.push_back(ban[i]); }
      |  ^
a.cc:104:2: error: stray '#' in program
  104 | &#160; now.push_back(c);
      |  ^
a.cc:105:2: error: stray '#' in program
  105 | &#160; while (!now.empty()) {
      |  ^
a.cc:106:2: error: stray '#' in program
  106 | &#160; &#160; now.pop_front();
      |  ^
a.cc:106:9: error: stray '#' in program
  106 | &#160; &#160; now.pop_front();
      |         ^
a.cc:107:2: error: stray '#' in program
  107 | &#160; &#160; REP(i, now.size()) {
      |  ^
a.cc:107:9: error: stray '#' in program
  107 | &#160; &#160; REP(i, now.size()) {
      |         ^
a.cc:108:2: error: stray '#' in program
  108 | &#160; &#160; &#160; if (now[i] != ban[i]) { goto next; }
      |  ^
a.cc:108:9: error: stray '#' in program
  108 | &#160; &#160; &#160; if (now[i] != ban[i]) { goto next; }
      |         ^
a.cc:108:16: error: stray '#' in program
  108 | &#160; &#160; &#160; if (now[i] != ban[i]) { goto next; }
      |                ^
a.cc:109:2: error: stray '#' in program
  109 | &#160; &#160; }
      |  ^
a.cc:109:9: error: stray '#' in program
  109 | &#160; &#160; }
      |         ^
a.cc:110:2: error: stray '#' in program
  110 | &#160; &#160; break;
      |  ^
a.cc:110:9: error: stray '#' in program
  110 | &#160; &#160; break;
      |         ^
a.cc:112:2: error: stray '#' in program
  112 | &#160; }
      |  ^
a.cc:113:2: error: stray '#' in program
  113 | &#160; return memo[pattern][c] = now.size();
      |  ^
a.cc:120:2: error: stray '#' in program
  120 | &#160; MEMSET(memo, -1);
      |  ^
a.cc:121:2: error: stray '#' in program
  121 | &#160; vector<bool> visit(n * len, false);
      |  ^
a.cc:122:2: error: stray '#' in program
  122 | &#160; queue<pair<int, int> > que;
      |  ^
a.cc:123:2: error: stray '#' in program
  123 | &#160; int first = color[0] == ban[0] ? 1 : 0;
      |  ^
a.cc:124:2: error: stray '#' in program
  124 | &#160; que.push(make_pair(0, first));
      |  ^
a.cc:125:2: error: stray '#' in program
  125 | &#160; Graph ret(n * len);
      |  ^
a.cc:126:2: error: stray '#' in program
  126 | &#160; if (len == first) { return ret; }
      |  ^
a.cc:127:2: error: stray '#' in program
  127 | &#160; while (!que.empty()) {
      |  ^
a.cc:128:2: error: stray '#' in program
  128 | &#160; &#160; int from = que.front().first;
      |  ^
a.cc:128:9: error: stray '#' in program
  128 | &#160; &#160; int from = que.front().first;
      |         ^
a.cc:129:2: error: stray '#' in program
  129 | &#160; &#160; int pattern = que.front().second;
      |  ^
a.cc:129:9: error: stray '#' in program
  129 | &#160; &#160; int pattern = que.front().second;
      |         ^
a.cc:130:2: error: stray '#' in program
  130 | &#160; &#160; que.pop();
      |  ^
a.cc:130:9: error: stray '#' in program
  130 | &#160; &#160; que.pop();
      |         ^
a.cc:131:2: error: stray '#' in program
  131 | &#160; &#160; if (visit[from * len + pattern]) { continue; }
      |  ^
a.cc:131:9: error: stray '#' in program
  131 | &#160; &#160; if (visit[from * len + pattern]) { continue; }
      |         ^
a.cc:1