原题直通车：HDU 4308 Saving Princess claire_
分析： 两次BFS分别找出‘Y’、‘C’到达最近的‘P’的最小消耗。再算出‘Y’到‘C’的最小消耗，比较出最小值
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<string>
using namespace std;
const int inf=0xFFFFFFF;
int n,m,k;
char f[5005][5005];
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int dis[5005][5005];
struct node{
int x,y,cost;
node(int a,int b,int c){
x=a, y=b, cost=c;
}
};
int BFS(node st,node et,int &p){
queue<node>M;
M.push(st);
while(!M.empty()){
node rt=M.front(); M.pop();
if(f[rt.x][rt.y]==f[et.x][et.y]) return rt.cost;
for(int i=0;i<4;++i){
node ne=rt;
ne.x+=dx[i], ne.y+=dy[i];
if(ne.x<0||ne.y<0||ne.x>=n||ne.y>=m||f[ne.x][ne.y]=='#') continue;
if(f[ne.x][ne.y]=='P'){
if(p>ne.cost) p=ne.cost;
continue;
}
if(f[ne.x][ne.y]=='*') ne.cost+=k;
if(ne.cost<dis[ne.x][ne.y]){
dis[ne.x][ne.y]=ne.cost;
M.push(ne);
}
}
}
return -1;
}
int main(){
while(~scanf("%d%d%d",&n,&m,&k)){
int ci,cj,yi,yj;
for(int i=0;i<n;++i){
scanf("%s",f[i]);
for(int j=0;j<m;++j){
if(f[i][j]=='C')
ci=i, cj=j;
else if(f[i][j]=='Y')
yi=i, yj=j;
dis[i][j]=inf;
}
}
node cc(ci,cj,0), yy(yi,yj,0);
int cp=inf, yp=inf;
int t1=BFS(cc,yy,cp);
int t2=BFS(yy,cc,yp);
if(t1==-1){
if(cp!=inf&&yp!=inf) printf("%d
",cp+yp);
else puts("Damn teoy!");
}
else {
if(cp!=inf&&yp!=inf&&t1>cp+yp) printf("%d
",cp+yp);
else printf("%d
",t1);
}
}
return 0;
}