www.pudn.com > travSrcCVar.rar > travSrcCVar.cpp
/* 汽车加油问题 2005-1-1 18:14 Release v1.0 2005-1-1 19:58 Release v1.0.1 修正输入时变转置 */ # include//# define MCOST 0xffffffff typedef unsigned long ulong; void writeData(ulong cost); ulong minpCost(int x, int y); ulong minppCost(int x1, int y1, int x2, int y2); void p2p(int x1, int y1, int x2, int y2); void pp2p(int x1, int y1, int x2, int y2, int x3, int y3); void renewUp(int x, int y); void renewDown(int x, int y); void renewLeft(int x, int y); void renewRight(int x, int y); int N, K, A, B, C; int level = 2; //起始层为起点 ulong MCOST = 0xffffffff; ulong cost[102][102][12]; int pos[102][102]; //存放加油站位置信息 int main(){ ifstream infile("input.txt"); if (!infile){ cout << "无法打开input.txt\n"; return -1; } infile >> N >> K >> A >> B >> C; //异常处理 if ( (N < 2) || (N > 100) || (K < 2) || (K > 10) || (A < 0) || (B < 0) || (C < 0) ){ cout << "输入数据有误\n"; return -1; } //正常处理 int ia, ib, ic; for (ia = 1; ia <= N; ia++){ for (ib = 1; ib <= N; ib++){ infile >> pos[ib][ia]; } } infile.close(); for (ia = 1; ia <= N; ia++){ for (ib = 1; ib <= N; ib++){ for (ic = 1; ic <= K; ic++) cost[ia][ib][ic] = MCOST; } } cost[1][1][K] = 0; //起点费用为0 for (level = 3; level <= N + 1; level++){ //处理上三角范围,含对角线level=N+1 p2p(level - 2, 1, level - 1, 1); //向y轴正向推进 p2p(1, level - 2, 1, level - 1); //向x轴正向推进 for (int id = level - 2; id >= 2; id--){ pp2p(id - 1, level - id, id, level - id - 1, id, level - id); //(id, level-id)点的左点和上点来更新 //从(id, level-id)开始倒退更新其余的点 renewUp(id, level - id - 1); renewLeft(id - 1, level - id); } } for (level = N + 2; level <= 2 * N - 1; level++){ //处理下三角范围,不含对角线 for (int id = level - N; id <= N; id++){ pp2p(id - 1, level - id, id, level - id - 1, id, level - id); //(id, level-id)点的左点和上点来更新 //从(id, level-id)开始倒退更新其余的点 renewUp(id, level - id - 1); renewLeft(id - 1, level - id); } } ulong mincost = minppCost(N, N - 1, N - 1, N); //最后两个点的最小费用就是到终点的最小费用 writeData(mincost); return 0; } void writeData(ulong cost){ ofstream outf("output.txt"); if (!outf) cout << "无法打开文件output.txt\n"; else{ cout << "最小费用是" << cost << endl; outf << cost; } outf.close(); } ulong minpCost(int x, int y){ ulong mincost = MCOST; for (int ir = 1; ir <= K; ir++) if (cost[x][y][ir] < mincost) mincost = cost[x][y][ir]; //如果mincost = MCOST则可能有异常 return mincost; } ulong minppCost(int x1, int y1, int x2, int y2){ ulong mc1 = minpCost(x1, y1); ulong mc2 = minpCost(x2, y2); return ( (mc1 < mc2) ? mc1 : mc2); } void p2p(int x1, int y1, int x2, int y2){ if (pos[x2][y2] == 0){ //不是加油站 for (int ir = 2; ir <= K; ir++){ if (cost[x1][y1][ir] == MCOST) //没有改进 continue; else cost[x2][y2][ir - 1] = cost[x1][y1][ir]; } if (cost[x1][y1][1] != MCOST) //设油库并加油 cost[x2][y2][K] = cost[x1][y1][1] + C + A; } else //(x2, y2)为加油站 cost[x2][y2][K] = minpCost(x1, y1) + A; } void pp2p(int x1, int y1, int x2, int y2, int x3, int y3){ if (pos[x3][y3] == 0){ //非加油站 for (int ir = 2; ir <= K; ir++) if ((cost[x1][y1][ir] == MCOST) && (cost[x2][y2][ir] == MCOST)) continue; else cost[x3][y3][ir - 1] = (cost[x1][y1][ir] < cost[x2][y2][ir]) ? cost[x1][y1][ir] : cost[x2][y2][ir]; cost[x3][y3][K] = (cost[x1][y1][1] < cost[x2][y2][1]) ? cost[x1][y1][1] : cost[x2][y2][1]; if (cost[x3][y3][K] != MCOST) cost[x3][y3][K] += C + A; } else{ //是加油站 cost[x3][y3][K] = minppCost(x1, y1, x2, y2) + A; } } void renewUp(int x, int y){ //从下向上, (x,y)为被更新的点 if (y == 0) return; //防止出界 bool isUpdate = false; if (pos[x][y] == 0){ //非加油站 for (int ir = 2; ir <= K; ir++) if (cost[x][y + 1][ir] == MCOST) continue; else if (cost[x][y][ir - 1] > cost[x][y + 1][ir] + B){ cost[x][y][ir - 1] = cost[x][y + 1][ir] + B; isUpdate = true; } if ( (cost[x][y + 1][1] != MCOST) && (cost[x][y][K] > cost[x][y + 1][1] + A + B + C ) ){ cost[x][y][K] = cost[x][y + 1][1] + A + B + C; isUpdate = true; } } else{ //是加油站 ulong tmp = minpCost(x, y + 1) + A + B; if (cost[x][y][K] > tmp){ cost[x][y][K] = tmp; isUpdate = true; } } if ( !isUpdate ) return; //无任何更新则返回 renewUp(x, y - 1); renewLeft(x - 1, y); renewRight(x + 1, y); } void renewDown(int x, int y){ //从上向下, (x,y)为被更新的点 if (x + y > level) return; //在已搜索过的上三角范围内更新 bool isUpdate = false; if (pos[x][y] == 0){ //非加油站 for (int ir = 2; ir <= K; ir++) if (cost[x][y - 1][ir] == MCOST) continue; else if (cost[x][y][ir - 1] > cost[x][y - 1][ir]){ cost[x][y][ir - 1] = cost[x][y - 1][ir]; isUpdate = true; } if ( (cost[x][y - 1][1] != MCOST) && (cost[x][y][K] > cost[x][y - 1][1] + A + C ) ){ cost[x][y][K] = cost[x][y - 1][1] + A + C; isUpdate = true; } } else{ //是加油站 ulong tmp = minpCost(x, y - 1) + A; if (cost[x][y][K] > tmp){ cost[x][y][K] = tmp; isUpdate = true; } } if ( !isUpdate ) return; //无任何更新则返回 renewDown(x, y + 1); renewLeft(x - 1, y); renewRight(x + 1, y); } void renewLeft(int x, int y){ //从右向左, (x,y)为被更新的点 if (x == 0) return; //防止出界 bool isUpdate = false; if (pos[x][y] == 0){ //非加油站 for (int ir = 2; ir <= K; ir++) if (cost[x + 1][y][ir] == MCOST) continue; else if (cost[x][y][ir - 1] > cost[x + 1][y][ir] + B){ cost[x][y][ir - 1] = cost[x + 1][y][ir] + B; isUpdate = true; } if ( (cost[x + 1][y][1] != MCOST) && (cost[x][y][K] > cost[x + 1][y][1] + A + B + C ) ){ cost[x][y][K] = cost[x + 1][y][1] + A + B + C; isUpdate = true; } } else{ //是加油站 ulong tmp = minpCost(x + 1, y) + A + B; if (cost[x][y][K] > tmp){ cost[x][y][K] = tmp; isUpdate = true; } } if ( !isUpdate ) return; //无任何更新则返回 renewUp(x, y - 1); renewDown(x, y + 1); renewLeft(x - 1, y); } void renewRight(int x, int y){ //从左向右, (x,y)为被更新的点 if (x + y > level) return; //在已搜索过的上三角范围内更新 bool isUpdate = false; if (pos[x][y] == 0){ //非加油站 for (int ir = 2; ir <= K; ir++) if (cost[x - 1][y][ir] == MCOST) continue; else if (cost[x][y][ir - 1] > cost[x - 1][y][ir]){ cost[x][y][ir - 1] = cost[x - 1][y][ir]; isUpdate = true; } if ( (cost[x - 1][y][1] != MCOST) && (cost[x][y][K] > cost[x - 1][y][1] + A + C ) ){ cost[x][y][K] = cost[x - 1][y][1] + A + C; isUpdate = true; } } else{ //是加油站 ulong tmp = minpCost(x - 1, y) + A; if (cost[x][y][K] > tmp){ cost[x][y][K] = tmp; isUpdate = true; } } if ( !isUpdate ) return; //无任何更新则返回 renewUp(x, y - 1); renewDown(x, y + 1); renewRight(x + 1, y); }