一道c语言的题目编号为1..N的N座城镇用若干仅供单向行驶的道路相连,每条道路上均有两个参数：道路长度(length)和在该条道路上行驶的费用（cost）.BOB准备从城镇1出发到达城镇N,但他目前只

一道c语言的题目编号为1..N的N座城镇用若干仅供单向行驶的道路相连,每条道路上均有两个参数：道路长度(length)和在该条道路上行驶的费用（cost）.BOB准备从城镇1出发到达城镇N,但他目前只
一道c语言的题目
编号为1..N的N座城镇用若干仅供单向行驶的道路相连,每条道路上均有两个参数：道路长度(length)和在该条道路上行驶的费用（cost）.BOB准备从城镇1出发到达城镇N,但他目前只有W的钱,为此,你需要帮助他寻找一条从城镇1到城镇N在他能支付的前提下的一条最短路线.
输入：
N K W（N为城镇数目,2

一道c语言的题目编号为1..N的N座城镇用若干仅供单向行驶的道路相连,每条道路上均有两个参数：道路长度(length)和在该条道路上行驶的费用（cost）.BOB准备从城镇1出发到达城镇N,但他目前只
#include <iostream>
using namespace std;

//记录两点间的路径
class lu
{
public:
//A点及B点
int pointA;
int pointB;
//路径长度
int lenth;
};

//点的集合
class inn
{
private:
public:
//用节点数初始化,本程序未用到
inn(int);
//直接初始化,以后要用ml(int);分配内存
inn();
//析构函数释放内存
~inn();
//根据节点个数分配内存
void ml(int);
//数据
int *data;
//有效元素个数
int len;
//新增元素
void add(int);
//删除元素
void cut(int);
};
//初始化（len均设为0,表示无数据）//
inn::inn(int n)        //
{//
data = new int[n];//
len = 0;//
}//
//
inn::inn()//
{//
len = 0;//
}//
//
inn::~inn()//
{//
delete[]data;//
}//
//
void inn::ml(int n)//
{//
data = new int[n];//
}//
//////////////////////////////


void inn::add(int d)
{
data[len++] = d;
}


void inn::cut(int d)
{
for (int i = 0; i<len - 1; ++i)
{
if (data[i] == d)
{
for (int j = i; j<len - 1; ++j)
{
data[j] = data[j + 1];
}
}
}
--len;
}

class Graph
{
private:
//节点个数
int n;
//无像图数据
int **G;
//源点
int s;
//没计算的点的集合
inn V;
//已计算的点的集合
inn S;
//路径
inn p;
//存储路径
string *pa;
public:
//用节点个数分配内存
Graph(int);
//析构函数释放内存
~Graph();
//设置源点
void SetSource(int);
//输入无像图邻接矩阵
void input();
//贪心算法求最短路径
void ALG();
//输出最短路径
void output();
};

Graph::Graph(int n)
{
this->n = n;
G = new int*[n];
for (int i = 0; i < n; i++)
{
G[i] = new int[n];
}
V.ml(n);
S.ml(n);
p.ml(n);
pa = new string[n];
}

Graph::~Graph()
{
for (int i = 0; i <n; i++)
{
delete[]G[i];
}
delete[]G;
delete[]pa;
}

void Graph::SetSource(int s)
{
this->s = s;
S.data[0] = s;
S.len = 1;
p.data[s] = 0;
p.len = 1;
int j(0);
for (int i = 0; i<n; ++i)
{
//源点除外
if (i != s)V.data[j++] = i;
}
V.len = n - 1;
}

void Graph::input()
{
for (int i = 0; i<n; ++i)
for (int j = 0; j<n; ++j)cin >> G[i][j];
}

void Graph::ALG()
{
while (S.len != n)
{
//定义临时变量
lu min;
//初始化临时变量,假设最短距离是已计算的第一个点和未计算的第一个点
min.pointA = S.data[0];
min.pointB = V.data[0];
min.lenth = G[S.data[0]][V.data[0]];
//找到未计算的距离已计算点的集合最近的点
for (int i = 0; i<S.len; ++i)
{
for (int j = 0; j<V.len; ++j)
{
//如果找到更短的
if (G[S.data[i]][V.data[j]]<min.lenth)
{
//记录有哪个点出发
min.pointA = S.data[i];
//记录到达哪个点
min.pointB = V.data[j];
//记录距离
min.lenth = G[S.data[i]][V.data[j]];
}
}
}
//新增的点的最短距离重新定义,或许还有更短的
//p.data[min.pointA] + min.lenth表示目前这条路径的长度
int min_ = p.data[min.pointA] + min.lenth;
char temp[10];
_itoa_s(min.pointB, temp,10, 10);
pa[min.pointB] = pa[min.pointA] + "->" + temp;
//在已计算的点中寻找是否有更短的路径
for (int i = 0; i < S.len; ++i)
{
//找到,替换当前路径长度
//若是无向图则也可以写成G[min.pointB][S.data[i]]
if (G[S.data[i]][min.pointB] + p.data[S.data[i]] < min_)
{
min_ = G[S.data[i]][min.pointB] + p.data[S.data[i]];
pa[min.pointB] = pa[i] + "->" + temp;
}
}
//记录路径长度
p.data[min.pointB] = min_;
//将新找到的点从未计算移到已计算,重复当前步骤,直到所有点都已计算
S.add(min.pointB);
V.cut(min.pointB);
}
}

void Graph::output()
{
for (int i = 0; i<n; ++i)
cout <<s<<"到"<<i<<":\n"<<s<<pa[i].c_str()<<"\n路径长度："<< p.data[i] << endl;
}

int main()
{
int n;
cout << "节点数:" << flush;
cin >> n;
Graph G(n);
cout << "矩阵：" << endl;
G.input();
int s;
cout << "源点：" << flush;
cin >> s;
G.SetSource(s);
G.ALG();
G.output();
getchar();
getchar();
}

这是我以前写的一个贪心算法求单源最短路径的源代码,你那程序也可用这个算法,自己慢慢琢磨吧

输入是以二维数组形式保存的邻接表,希望对你有帮助,多读些代码有好处哦,你这个程序懒得写,耗时间,你自己写写试吧,到网上找些类似的看看,学编程一定要自己动手才会有进步哦