#include <cstdio>#include <cstring>#include <queue>using namespace std;const int MAXN = 110;const int MAXE = MAXN * MAXN * 2;const int INF = 0x7f7f7f7f;struct Dinic { int n, m, st, ed, ecnt; int head[MAXN]; int cur[MAXN], d[MAXN]; int to[MAXE], next[MAXE], flow[MAXE], cap[MAXE]; void init(int ss, int tt, int nn) { st = ss; ed = tt; n = nn; ecnt = 2; memset(head, 0, sizeof(head)); } void add_edge(int u, int v, int c) { to[ecnt] = v; cap[ecnt] = c; flow[ecnt] = 0; next[ecnt] = head[u]; head[u] = ecnt++; to[ecnt] = u; cap[ecnt] = 0; flow[ecnt] = 0; next[ecnt] = head[v]; head[v] = ecnt++; } bool bfs() { memset(d, 0, sizeof(d)); queue<int> que; que.push(st); d[st] = 1; while(!que.empty()) { int u = que.front(); que.pop(); for(int p = head[u]; p; p = next[p]) { int v = to[p]; if(!d[v] && cap[p] > flow[p]) { d[v] = d[u] + 1; que.push(v); if(v == ed) return true; } } } return d[ed]; } int dfs(int u, int a) { if(u == ed || a == 0) return a; int outflow = 0, f; for(int &p = cur[u]; p; p = next[p]) { int v = to[p]; if(d[u] + 1 == d[v] && (f = dfs(v, min(a, cap[p] - flow[p]))) > 0) { flow[p] += f; flow[p ^ 1] -= f; outflow += f; a -= f; if(a == 0) break; } } return outflow; } int Maxflow() { int ans = 0; while(bfs()) { for(int i = 0; i <= n; ++i) cur[i] = head[i]; ans += dfs(st, INF); } return ans; }} G;int mat[MAXN][MAXN];int st[MAXN][MAXN];#define REP(i, t) for(int i = 1; i <= t; ++i)void floyd(int n) { REP(k, n) REP(i, n) REP(j, n) { if(st[i][k] == -1 || st[k][j] == -1) continue; if(st[i][j] == -1 || st[i][j] > st[i][k] + st[k][j]) st[i][j] = st[i][k] + st[k][j]; }}int main() { int n, s, t; while(scanf("%d", &n) != EOF) { REP(i, n) REP(j, n) { scanf("%d", &mat[i][j]); st[i][j] = mat[i][j]; } REP(i, n) st[i][i] = mat[i][i] = 0; scanf("%d%d", &s, &t); ++s, ++t; if(s == t) { printf("infn"); continue; } floyd(n); G.init(s, t, n); REP(i, n) REP(j, n) if(i != j && mat[i][j] != -1 && st[s][i] != -1 && st[j][t] != -1 && st[s][t] == st[s][i] + mat[i][j] + st[j][t]) G.add_edge(i, j, 1); printf("%dn", G.Maxflow()); }}
