Question

一道c语言的题目

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

输入：
N K W（N为城镇数目，2<=N<=100，K为道路条数，1<=K<=10000,W为钱的数目， 0<=w<=1000）
随后的K行每行为一条道路的信息，包含4个数值（S,D,L,T）其中S为源城镇，D为目标城镇，L为道路长度，T为所需支付用。（1<=S,D<=N,1<=L<=100,0<=T<=100）

输出：
输出最短长度，若无解，则输出“NO”；

示例：
roads.in
6 7 5
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

roads.out
11

Answer 1

#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();
}

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

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

Answer 2

by rightisttree
roads
from summercamp 2011
｝
type
arr=array[0..200,0..200] of longint;
node=record
len:longint;
w:longint;
end;
arr2=array[0..200,0..200] of node;

var
a:arr2;
g:arr;
visited:array[0..200] of boolean;
i,j,n,k,w,ans,min,sum,s,d,l,t:longint;

procedure floyd;
var
i,j,k:integer;

begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
begin
if (i=k) or (j=k) or (i=j) then continue;
if (g[i,k]<maxlongint)
and (g[k,j]<maxlongint)
and (g[i,k]+g[k,j]<g[i,j])
then g[i,j]:=g[i,k]+g[k,j];
end;
end;

procedure dfs(depth,length,cost:longint);
var
i:integer;

begin
if depth=n then
begin
if (length<min) and (cost<=w) then
begin
min:=length;
ans:=cost;
inc(sum);
end
end
else if cost+g[depth,n]>w then exit
else
begin

for i:=1 to n do
if (not visited[i]) and (a[depth,i].len<maxlongint) then
begin
visited[depth]:=true;
dfs(i,length+a[depth,i].len,cost+a[depth,i].w);
visited[depth]:=false;
end;
end;
end;

begin //main
//assign(input,'roads.in'); reset(input);

readln(n,k,w);
for i:=0 to n do for j:=0 to n do begin a[i,j].len:=maxlongint;a[i,j].w:=maxlongint;end;
for i:=1 to n do visited[i]:=false;
for i:=1 to k do begin readln(s,d,l,t);a[s,d].len:=l;a[s,d].w:=t; end;
//close(input);
for i:=1 to n do for j:=1 to n do g[i,j]:=a[i,j].w;
floyd;
ans:=maxlongint; min:=maxlongint; sum:=0; visited[1]:=true;
dfs(1,0,0);

//assign(output,'roads.out'); rewrite(output);
if sum<>0 then writeln(min)
else writeln('NO');
//close(output);
end.

Answer 3

boost graph library
你应当是专门学这个的吧 书上应该有算法 可以自己写啊

追问

但是写起来有问题，想看看别人写的