缩边很强，主要是方案数比较难搞，因为两条路不同有且仅当走过的空格不同，那么我们应该消除实际边权为0的影响。
首先，假设有一个集合全是1点，并且可以互相间接或直接到达，那么一条路径伸到此点集中没必要边权为0的在里面绕，不管怎么绕都是一种情况。缩点解决。
其次，只有缩点真的可以吗，
考虑一张简单的图，3到4可以走右下的1点集合，再走到(2,2)的0点最后到达4，也可以直接跳到(2,2)的0点。但因为走过的0点一样，其实算一个方案。
这时就能发现漏洞了，因为缩完点的点作为了一个路径上独立的点来区分了走过它和不走过它的路径，这和题意不符，我们只考虑0点的对路径区分的独立性。
想办法，既然是1点的锅，我们就要让他负责。他必然不能出现在路径上，所以考虑把他删掉，然而原来联通的路径，例如0点到1点再到0点，应该提前预处理出0点到0点。
注意不能将4和1合并，应该把4当成0点建边以确保终点联通的正确性，最后最短路-1即可。
1 #include<bits/stdc++.h> 2 #define MAXN 2510 3 #define INF (1ll<<60) 4 #define ll long long 5 using namespace std; 6 struct rr{ 7 int nt,to; 8 ll w; 9 }bl[MAXN*MAXN];int hd[MAXN],itot; 10 void add(int x,int y,int z){ 11 for(int i=hd[x];i;i=bl[i].nt) 12 if(bl[i].to==y)return ; 13 bl[++itot].to=y; 14 bl[itot].w=z; 15 bl[itot].nt=hd[x]; 16 hd[x]=itot; 17 } 18 int st,en; 19 int jz[60][60]; 20 int fat[MAXN]; 21 inline int find(int x){ 22 if(!fat[x]||fat[x]==x)return x; 23 return fat[x]=find(fat[x]); 24 } 25 int n,m; 26 inline int zh(int i,int j){return (i-1)*m+j; } 27 vector<vector<int > >td(MAXN); 28 ll dist[MAXN],cnt[MAXN]; 29 bool vis[MAXN]; 30 queue<int >dd; 31 bool pd[MAXN]; 32 void spfa(){ 33 for(int i=1;i<=n*m;++i)dist[i]=INF; 34 dd.push(st); 35 vis[st]=1;dist[st]=0;cnt[st]=1; 36 while(!dd.empty()){ 37 int ltop=dd.front();dd.pop(); 38 vis[ltop]=0; 39 for(int i=hd[ltop];i;i=bl[i].nt) 40 if(dist[bl[i].to]>dist[ltop]+bl[i].w){ 41 dist[bl[i].to]=dist[ltop]+bl[i].w; 42 cnt[bl[i].to]=cnt[ltop]; 43 if(!vis[bl[i].to]){ 44 vis[bl[i].to]=1; 45 dd.push(bl[i].to); 46 } 47 } 48 else if(dist[bl[i].to]==dist[ltop]+bl[i].w) 49 cnt[bl[i].to]+=cnt[ltop]; 50 } 51 } 52 int fx[8][2]; 53 int main(){ 54 //freopen("da.in","r",stdin); 55 //freopen("hh.out","w",stdout); 56 scanf("%d%d",&n,&m); 57 58 fx[0][0]=2;fx[0][1]=1; 59 fx[1][0]=2;fx[1][1]=-1; 60 fx[2][0]=-2;fx[2][1]=1; 61 fx[3][0]=-2;fx[3][1]=-1; 62 63 fx[4][0]=1;fx[4][1]=2; 64 fx[5][0]=-1;fx[5][1]=2; 65 fx[6][0]=1;fx[6][1]=-2; 66 fx[7][0]=-1;fx[7][1]=-2; 67 68 for(int i=1;i<=n;++i) 69 for(int j=1;j<=m;++j){ 70 scanf("%d",&jz[i][j]); 71 if(jz[i][j]==3){ 72 st=zh(i,j);jz[i][j]=0; 73 } 74 else if(jz[i][j]==4){ 75 en=zh(i,j);jz[i][j]=0; 76 } 77 if(jz[i][j]==1){ 78 int ti,tj; 79 for(int k=0;k<8;++k){ 80 ti=i+fx[k][0];tj=j+fx[k][1]; 81 if(ti<1||ti>n)continue; 82 if(tj<1||tj>m)continue; 83 if(jz[ti][tj]==1) 84 fat[find(zh(ti,tj))]=find(zh(i,j)); 85 } 86 } 87 } 88 for(int i=1;i<=n;++i) 89 for(int j=1;j<=m;++j){ 90 int ti,tj; 91 for(int k=0;k<8;++k){ 92 ti=i+fx[k][0];tj=j+fx[k][1]; 93 if(ti<1||ti>n)continue; 94 if(tj<1||tj>m)continue; 95 if(!jz[i][j]&&!jz[ti][tj]) 96 add(find(zh(i,j)),find(zh(ti,tj)),1); 97 if(jz[i][j]==1&&!jz[ti][tj]) 98 td[find(zh(i,j))].push_back(find(zh(ti,tj))); 99 } 100 } 101 /*for(int i=1;i<=n;++i){ 102 for(int j=1;j<=m;++j) 103 printf("%3d",find(zh(i,j))); 104 cout<<endl; 105 }*/ 106 for(int i=1;i<=n*m;++i) 107 if(td[i].size()) 108 for(int k=0;k<td[i].size();++k){ 109 //cout<<td[i][k]<<endl; 110 for(int s=k+1;s<td[i].size();++s){ 111 add(td[i][k],td[i][s],1); 112 add(td[i][s],td[i][k],1); 113 } 114 } 115 /*for(int i=1;i<=n*m;++i){ 116 for(int j=hd[i];j;j=bl[j].nt) 117 cout<<i<<" "<<bl[j].to<<" "<<bl[j].w<<endl; 118 }*/ 119 st=find(st); 120 en=find(en); 121 spfa(); 122 if(dist[en]==INF)puts("-1"); 123 else printf("%lld\n%lld\n",dist[en]-1,cnt[en]); 124 }
原文：https://www.cnblogs.com/2018hzoicyf/p/11354492.html
