租用游艇问题(C或C )
#include #include using namespace std;#define INFINITE 2000int main(){ ifstream infile("input1。txt"); if (!infile) { cerr > numOfSite; int *matrix = new int[numOfSite * numOfSite]; int *arrPrevious = new int[numOfSite]; //记录到该站点的最小租金的前一个站点 //读入租金值 for (int i = 0; i != numOfSite; i) { for (in...全部
#include #include using namespace std;#define INFINITE 2000int main(){ ifstream infile("input1。txt"); if (!infile) { cerr > numOfSite; int *matrix = new int[numOfSite * numOfSite]; int *arrPrevious = new int[numOfSite]; //记录到该站点的最小租金的前一个站点 //读入租金值 for (int i = 0; i != numOfSite; i) { for (int j = 0; j != numOfSite; j) { infile >> matrix[i * numOfSite j]; if (-1 == matrix[i * numOfSite j]) //在文件中用-1表示无穷 { matrix[i * numOfSite j] = INFINITE; //无穷代表不连通 } } } infile。
clear(); infile。close(); //第一站的前一站为无 arrPrevious[0] = -1; //第一站到第二站有路径可达时 ,第二站的前一站就为1 arrPrevious[1] = (INFINITE == matrix[1]) ? -1: 0; //计算最少1站到各个站的最少租金，结果在矩阵第一行 for (int cul = 2; cul != numOfSite; cul) //第三列开始 { if (matrix[cul] == INFINITE) { arrPrevious[cul] = -1; } else { arrPrevious[cul] = 0; //初始为第一个站点 } for (int row = 1; row != cul; row) // 第二行开始,上三角 { //如果第row站到cul站的距离加上第一站到第row站的距离 //比第一站到第cul站的最小距离还小的话就替换 //当有多条路径时, " if (matrix[row * numOfSite cul] matrix[row] { arrPrevious[cul] = row; matrix[cul] = matrix[row * numOfSite cul] matrix[row]; } } } //第一站1到第numOfSite站的最少租金就在matrix[0][numOfSite - 1]中 ofstream outfile("output。
txt"); if (!outfile) { cerr return -1; } outfile outfile int iLast = numOfSite - 1; //下标从零开始,例如下标为4代表站点5 int iCnt = 2; //记录经过的站点的个数 ,2就代表一开始包含两个站点(第一个,最后一个) //以为主要为记录站点的个数,方便动态分配内存大小 while ( true ) { iLast = arrPrevious[iLast]; if (iLast == -1) { cout system("pause"); return -1; } if (iLast == 0) { break; } iCnt; } iLast = numOfSite - 1; int iPathNum = iCnt; int *arrPath = new int[iPathNum]; while ( true ) { arrPath[--iCnt] = iLast 1; iLast = arrPrevious[iLast]; if (0 == iLast) { arrPath[--iCnt] = iLast 1; break; } } outfile for (int site = 0; site != iPathNum; site) { outfile } outfile delete[]matrix; delete[]arrPrevious; delete[]arrPath; outfile。
close(); system("pause"); return 0;}。收起
