http://acm.timus.ru/problem.aspx?space=1&num=1254
刚开始想多了 依次spfa就可以
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<map> #include<vector> #include<stack> #include<set> #include<map> #include<queue> #include<algorithm> #include<cmath> #define LL long long #define sint short int //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const int N=1005; const int INF=0x7fffffff; typedef pair<int,int>point; int X[]={-1,-1,-1,0,0,1,1,1}; int Y[]={-1,0,1,-1,1,-1,0,1}; double L[]={sqrt(2.0),1.0,sqrt(2.0),1.0,1.0,sqrt(2.0),1.0,sqrt(2.0)}; point p[N]; char s[N][N]; bool in[N][N]; double dist[N][N]; void init(int n,int k) { getchar(); for(int i=0;i<n;++i) gets(s[i]); for(int i=0;i<=k;++i) { scanf("%d %d",&p[i].second,&p[i].first); --p[i].first;--p[i].second; } } double spfa(int n,int m,int x1,int y1,int x2,int y2) { memset(in,false,sizeof(in)); for(int i=0;i<n;++i) for(int j=0;j<m;++j) dist[i][j]=-1.0; queue<int>qtx,qty; dist[x1][y1]=0.0; in[x1][y1]=true; qtx.push(x1); qty.push(y1); while(!qtx.empty()) { int x=qtx.front();qtx.pop(); int y=qty.front();qty.pop(); in[x][y]=false; for(int i=0;i<8;++i) { int l1=x+X[i]; int l2=y+Y[i]; if(l1>=0&&l1<n&&l2>=0&&l2<m&&s[l1][l2]=='.') { if(dist[l1][l2]<0.0||dist[l1][l2]>dist[x][y]+L[i]) { dist[l1][l2]=dist[x][y]+L[i]; if(!in[l1][l2]) { in[l1][l2]=true; qtx.push(l1); qty.push(l2); } } } } } return dist[x2][y2]; } double solve(int n,int m,int k) { double sum=0; int l=0,r=1; while(r<=k) { double tmp=spfa(n,m,p[l].first,p[l].second,p[r].first,p[r].second); //cout<<tmp<<endl; if(tmp<=0) ++r; else {l=r;++r;sum+=tmp;} } return sum; } int main() { //freopen("data.in","r",stdin); int n,m,k; double v; while(cin>>m>>n>>k>>v) { init(n,k); printf("%.2lf\n",solve(n,m,k)/v); } }