Nothing up here. The good stuff is below.
Powered by Randall
#include <iostream>
#include <vector>
using namespace std;
int minnum(int a,int b,int c){//get the min number
int n=a;
if(a>b){
n=b;
}
if(n>c){
n=
读取数组定义了三个个vector容器，将数值存入容器后再将容器转换为普通数组。函数上面对于该算法的分析，求解过程实际上是典型的动态规划解题过程，描述最优子结构：公式的推倒，思考过程，得到一个递归解，按自底向上的方式计算最优解：最短路径权值矩阵。最后有计算结果构造一个最优解，给出最短路径。
c;
}
return n;
}
int maxinarr(int a[], int size){
int n=a[0];
for(int i=1;i<size;i++){
if(n<a[i])
n=a[i];
}
return n;
}
int mininarr(int a[], int size){
int n=a[0];
for(int i=1;i<size;i++){
if(n>a[i])
n=a[i];
}
return n;
}
int main(){
vector<int> startpoint;
vector<int> endpoint;
vector<int> weight;
int number;
cout << "请依次输入每段路经的起始点，结束点和权值（输入-1结束输入ps:-1所在行数字无效）：" << endl;
while (1) {
cin >> number;
if (number == -1)//如果是-1则跳出循环
break;
startpoint.push_back(number);//每输入一个数字就把它添加到数组的最后
cin >> number;
if (number == -1)
break;
endpoint.push_back(number);
cin >> number;
if (number == -1)
break;
weight.push_back(number);
}
int *sp = new int[startpoint.size()];
if (!startpoint.empty()){
memcpy(sp, &startpoint[0], startpoint.size()*sizeof(int));
}
int *ep = new int[endpoint.size()];
if (!endpoint.empty()){
memcpy(ep, &endpoint[0], endpoint.size()*sizeof(int));
}
int *wt = new int[weight.size()];
if (!weight.empty()){
memcpy(wt, &weight[0], weight.size()*sizeof(int));
}
int size=minnum(startpoint.size(),endpoint.size(),weight.size());
int max=maxinarr(ep,size);
if(maxinarr(sp,size)>maxinarr(ep,size))
int max=maxinarr(sp,size);
int sheet[max+1][max+1];
int min=mininarr(ep,size);
if(mininarr(sp,size)>mininarr(ep,size))
int min=mininarr(sp,size);
for(int i=min;i<=max;i++){
for(int j=min;j<=max;j++){
sheet[i][j]=99999;
}
}
//比较存入路径长短后存入数据
for(int i=0;i<size;i++){
if(sheet[sp[i]][ep[i]]>wt[i]){
sheet[sp[i]][ep[i]]=wt[i];
}
}
cout<<"排序前："<< endl;
for(int i=min;i<=max;i++){
for(int j=min;j<=max;j++){
cout << sheet[i][j]<<" ";
}
cout << endl;
}
//循环计算最短路径表
for(int k=min;k<=max;k++){
for(int i=min;i<=max;i++){
for(int j=min;j<=max;j++){
if(sheet[i][j]>sheet[i][k]+sheet[k][j])
sheet[i][j]=sheet[i][k]+sheet[k][j];
}
}
}
cout<<"排序后："<< endl;
for(int i=min;i<=max;i++){
for(int j=min;j<=max;j++){
cout << sheet[i][j]<<" ";
}
cout << endl;
}
cout << endl;
cout << " ";
for(int i=min;i<=max;i++){
printf("%10d",i);
}
cout << endl;
for(int i=min;i<=max;i++){
for(int j=min-1;j<=max;j++){
if(j==min-1){
printf("%10d",i);
continue;
}
printf("%10d",sheet[i][j]);
}
cout << endl;
}
}