//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "斯坦纳树  (游览计划)": {
        "prefix": "acm-4.3方格图",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#include<queue>",
            "#define LL long long",
            "#define Re register int",
            "using namespace std;",
            "const int N=12;",
            "int n,m,ct,A[N][N],B[N][N];",
            "inline void in(Re &x){",
            "    int f=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')f|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=f?-x:x;",
            "}",
            "struct Steiner_Tree{",
            "\tstruct PRE{int i,j,s;PRE(Re I=0,Re J=0,Re S=0){i=I,j=J,s=S;}}pre[N][N][1024+3];",
            "\tint vis[N][N],dp[N][N][1024+3],wx[4]={-1,0,1,0},wy[4]={0,1,0,-1};",
            "\tstruct QAQ{int x,y;QAQ(Re X=0,Re Y=0){x=X,y=Y;}};",
            "\tqueue<QAQ>Q;",
            "\tinline void SPFA(Re s){",
            "\t\twhile(!Q.empty()){",
            "\t\t\tQAQ now=Q.front();Q.pop();",
            "\t\t\tRe x=now.x,y=now.y;vis[x][y]=0;",
            "\t\t\tfor(Re o=0;o<4;++o){",
            "\t\t\t\tRe nx=x+wx[o],ny=y+wy[o];",
            "\t\t\t\tif(nx<1||nx>n||ny<1||ny>m)continue;",
            "\t\t\t\tif(dp[nx][ny][s]>dp[x][y][s]+B[nx][ny]){",
            "\t\t\t\t\tdp[nx][ny][s]=dp[x][y][s]+B[nx][ny],pre[nx][ny][s]=PRE(x,y,s);",
            "\t\t\t\t\tif(!vis[nx][ny])Q.push(QAQ(nx,ny)),vis[nx][ny]=1;",
            "\t\t\t\t}",
            "\t\t\t}",
            "\t\t}",
            "\t}",
            "\tint Ans[N][N];",
            "\tinline void dfs(Re i,Re j,Re s){",
            "\t\tAns[i][j]=1;PRE to=pre[i][j][s];",
            "\t\tif(to.s){",
            "\t\t\tdfs(to.i,to.j,to.s);",
            "\t\t\tif(to.i==i&&to.j==j)dfs(to.i,to.j,s^to.s);",
            "\t\t}",
            "\t}",
            "\tinline void sakura(){",
            "\t\tmemset(dp,63,sizeof(dp));",
            "\t\tRe V=(1<<ct)-1,inf=dp[0][0][0];",
            "\t\tfor(Re i=1;i<=n;++i)",
            "\t\t\tfor(Re j=1;j<=m;++j)",
            "\t\t\t\tif(A[i][j])dp[i][j][1<<A[i][j]-1]=0;",
            "\t\tfor(Re s=0;s<=V;++s){",
            "\t\t\tfor(Re i=1;i<=n;++i)",
            "\t\t\t\tfor(Re j=1;j<=m;++j){",
            "\t\t\t\t\tfor(Re t=(s-1)&s,tmp;t;t=(t-1)&s)",
            "\t\t\t\t\t\tif((tmp=dp[i][j][t]+dp[i][j][s^t]-B[i][j])<dp[i][j][s])",
            "\t\t\t\t\t\t\tdp[i][j][s]=tmp,pre[i][j][s]=PRE(i,j,t);",
            "\t\t\t\t\tif(dp[i][j][s]!=inf)Q.push(QAQ(i,j)),vis[i][j]=1;",
            "\t\t\t\t}",
            "\t\t\tSPFA(s);",
            "\t\t}",
            "\t\tRe ans=2e9,x,y;",
            "\t\tfor(Re i=1;i<=n;++i)",
            "\t\t\tfor(Re j=1;j<=m;++j)",
            "\t\t\t\tif(A[i][j])ans=dp[x=i][y=j][V];",
            "\t\tprintf(\"%d\\n\",ans);",
            "\t\tdfs(x,y,V);",
            "\t\tfor(Re i=1;i<=n;puts(\"\"),++i)",
            "\t\t\tfor(Re j=1;j<=m;++j)",
            "\t\t\t\tputchar(A[i][j]?'x':(Ans[i][j]?'o':'_'));",
            "\t}",
            "}T1;",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tin(n),in(m);",
            "\tfor(Re i=1;i<=n;++i)",
            "\t\tfor(Re j=1;j<=m;++j){",
            "\t\t\tin(B[i][j]);",
            "\t\t\tif(!B[i][j])A[i][j]=++ct;",
            "\t\t}",
            "\tT1.sakura();",
            "}",
            ""
        ],
        "description": "插入 斯坦纳树  (游览计划)"
    }
}