题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1632
题意：
有一个n*m的池塘。0代表水，1代表荷花，2代表岩石，3代表起点，4代表终点。
Bessie在练芭蕾舞，她要从起点跳到终点去。
她只能走“日”字形，并且只能跳到荷花上。
荷花不能长在岩石上。
问你：
（1）至少要再添加多少个荷花，才能使Bessie可以跳到终点。
（2）在（1）的前提下，让Bessie跳到终点的步数最小，并输出。
（3）在（1）（2）条件下的路径条数。
题解：
方便起见，对于每个点(x,y)可以表示成x*m+y的形式，即平面上的点在实数上的唯一映射。
第一问：
建图。
对于每个点，到水建一条边长为1的边，到荷花建一条边长为0的边。
跑一边spfa，第一问就出来了。
第二问：
在spfa中更新dis的时候，分两种情况：
（1）dis[dest]==-1 || dis[dest]>dis[now]+len
此时dis被更新，相应的step[dest]一定要变成step[now]+1。
（2）dis[dest]==dis[now]+len
dis未被更新，但step有可能更优，step[dest] = min(step[dest], step[now]+1)
第三问：
在前两问都不变的情况下，才有可能 cnt[dest] += cnt[now]。
否则cnt[dest] = cnt[now]
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define MAX_N 35
#define MAX_P 905 using namespace std; const int dx[]={-,-,-,-,,,,};
const int dy[]={-,,-,,-,,-,}; struct Edge
{
int dest;
int len;
Edge(int _dest,int _len)
{
dest=_dest;
len=_len;
}
Edge(){}
}; int n,m;
int start,over;
int dis[MAX_P];
int step[MAX_P];
long long cnt[MAX_P];
int a[MAX_N][MAX_N];
bool vis[MAX_P];
vector<Edge> edge[MAX_P];
queue<int> q; void read()
{
cin>>n>>m;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]==) start=i*m+j;
if(a[i][j]==) over=i*m+j;
}
}
} inline bool is_legal(int x,int y)
{
return x>= && x<n && y>= && y<m;
} void build_graph()
{
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
for(int k=;k<;k++)
{
int x=i+dx[k];
int y=j+dy[k];
if(is_legal(x,y) && a[x][y]!=)
{
edge[i*m+j].push_back(Edge(x*m+y,a[x][y]==));
}
}
}
}
} int get_front()
{
int now=q.front();
q.pop();
vis[now]=false;
return now;
} void insert(int now)
{
if(vis[now]) return;
q.push(now);
vis[now]=true;
} void spfa(int start)
{
memset(dis,-,sizeof(dis));
memset(step,0x3f,sizeof(step));
memset(cnt,,sizeof(cnt));
memset(vis,false,sizeof(vis));
insert(start);
dis[start]=;
step[start]=;
cnt[start]=;
while(!q.empty())
{
int now=get_front();
for(int i=;i<edge[now].size();i++)
{
Edge temp=edge[now][i];
if(dis[temp.dest]==- || dis[temp.dest]>dis[now]+temp.len)
{
dis[temp.dest]=dis[now]+temp.len;
step[temp.dest]=step[now]+;
cnt[temp.dest]=cnt[now];
insert(temp.dest);
}
else if(dis[temp.dest]==dis[now]+temp.len)
{
if(step[temp.dest]>step[now]+)
{
step[temp.dest]=step[now]+;
cnt[temp.dest]=cnt[now];
insert(temp.dest);
}
else if(step[temp.dest]==step[now]+)
{
cnt[temp.dest]+=cnt[now];
insert(temp.dest);
}
}
}
}
} void solve()
{
build_graph();
spfa(start);
} void print()
{
cout<<dis[over]<<endl;
if(dis[over]!=-)
{
cout<<step[over]<<endl;
cout<<cnt[over]<<endl;
}
} int main()
{
read();
solve();
print();
}