#include <fstream>
#include <iostream>
using namespace std;
#define INFINITE 2000
int main()
{
ifstream infile(input1.txt);
if (!infile)
{
cerr << open input file error! << endl;
return -1;
}
int numOfSite; //出租站个数
infile >> 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] < matrix[cul])
{
arrPrevious[cul] = row;
matrix[cul] = matrix[row * numOfSite + cul] + matrix[row];
}
}
}
//第一站1到第numOfSite站的最少租金就在matrix[0][numOfSite - 1]中
ofstream outfile(output.txt);
if (!outfile)
{
cerr << open the output file error! << endl;
return -1;
}
outfile << 最少租金为: << endl;
outfile << matrix[numOfSite - 1] << endl;
int iLast = numOfSite - 1; //下标从零开始,例如下标为4代表站点5
int iCnt = 2; //记录经过的站点的个数 ,2就代表一开始包含两个站点(第一个,最后一个)
//以为主要为记录站点的个数,方便动态分配内存大小
while ( true )
{
iLast = arrPrevious[iLast];
if (iLast == -1)
{
cout << 不可达 << endl;
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 << 路径如下: << endl;;
for (int site = 0; site != iPathNum; ++site)
{
outfile << arrPath[site] << ;
}
outfile << endl;
delete[]matrix;
delete[]arrPrevious;
delete[]arrPath;
outfile.close();
system(pause);
return 0;
}
WI游艇租赁公司专长于带船员的豪华游艇包租服务，提供奢华大帆船、动力游艇及超级游艇的租赁，涉及全球最美丽的海域，地中海，加勒比海，印度洋，南太平洋，亚洲地区等。
地中海地区包括：
西地中海
科西嘉岛 法国 西班牙 巴塞罗那 白色海岸
意大利 热那亚 里古利亚 那不勒斯 萨勒诺 罗马 撒丁岛 西西里 托斯卡尼 威尼斯
东地中海
克罗地亚 达尔马提亚 史普里特 杜布罗夫尼克 北克罗地亚
希腊 雅典 基克拉底 多得卡尼斯 爱奥尼亚海
土耳其
加勒比海地区: 美国，巴西，巴拿马，巴哈马群岛，委内瑞拉
印度洋地区：塞舌尔，马尔代夫，马达加斯加
亚洲地区： 泰国，马来西亚，印度尼西亚，巴厘岛，缅甸,新加坡，香港
太平洋地区：波利尼西亚，澳大利亚，新西兰，斐济，汤加
#include <iostream>
using namespace std;
int cal( int nn,int **aa )
{
int cost=aa[1][nn];
if ( nn==2 )
return cost;
else
{
for ( int i=2; i<nn; i++)
if( cost > ( cal( i, aa )+aa[i][nn] ) )
cost=( cal( i, aa )+aa[i][nn] );
return cost;
}
}
int main()
{
int i,j,n;
cin >> n;
int **a=new int*[n];
for( i=0; i<n; i++)
a[i]=new int[n+1];
for ( i=0; i<n; i++)
for( j=0; j<n+1; j++)
a[i][j]=0;
for ( i=1; i<n; i++ )
for ( j=i+1; j<=n; j++)
cin >> a[i][j];
cout << cal( n,a ) << endl;
return 0;
}
#include <iostream>
using namespace std;
int CalCharge(int *iCharge, int *iTotal, int num, int total);
int main()
{
int count;
cin >> count;
if (count <= 1)
return 1;
int *iCharge = new int[count * count];
int *iTotal = new int[count];
int result = 0;
int *iCharge1 = iCharge;
int *iTotal1 = iTotal;
for (int i=0; i<count*count; i++)
*(iCharge1++) = 0;
for (int i=0; i<count; i++)
*(iTotal1++) = 0;
result = 0;
for (int i=0; i<(count-1); i++)
{
iCharge1 = iCharge + i*count;
for (int j=(i+1); j<count; j++)
{
cin >> *(iCharge1 + j);
}
}
for (int i=(count-2); i>=0; i--)
{
*(iTotal + i) = CalCharge(iCharge, iTotal, i, count);
}
result = *iTotal;
cout << result << endl;
delete[] iCharge;
delete[] iTotal;
return 0;
}
int CalCharge(int *iCharge, int *iTotal, int num, int total)
{
iCharge += num * total;
int min = INT_MAX;
for (int i=(num+1); i<total; i++)
{
int temp = (*(iCharge + i)) + (*(iTotal + i));
if (temp < min)
min = temp;
}
return min;
}