...及求任意两个站点间的最短路径和换乘方法。

发布网友 发布时间：2024-10-24 09:49

我来回答

共1个回答

热心网友 时间：2天前

这是我写的程序和运行的结果，如果有不会的地方依然可以问我。
/*
首先我想说明几点问题。
1.我不知道你的题意中的路径是单向的还是双向的，不过我把路径设置成双向的了
2.说一下我程序的输入，首先输入一个n，表示该图中有n条路；然后有n行，每行
两个数x, y（1<=x, y<=99），表示这两个地点有一条路径。最后输入两个数，
表示计算这两点之间所有的路径
3.我的思路用的是深搜，不过广搜也是可以的
*/
#include <stdio.h>
#include <math.h>
int path[100][100];///path[i][j]为0表示i, j两点之间不通，为1表示有一条路
int stack[120], m=1, n, x, y;///存储路径
void dfs(int p)
{
int i, j;
for(i=1; i<=100; i++)
{
if(path[p][i]==1)
{
if(i == y)///如果深搜到了终点，就输出刚才经过的路径
{
for(j=0; j<m; j++)
{
printf("%-5d", stack[j]);
}
printf("%-5d\n", y);
}
else///如果该点不是终点
{
stack[m] = i;///将该点存起来
m++;
dfs(i);///接着深搜
m--;
}
}
}
}
int main()
{
int i, j;
memset(path, 0, sizeof(path));
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d %d", &x, &y);
path[x][y] = path[x][y] = 1;///这两点之间有路径
}
scanf("%d %d", &x, &y);
stack[0] = x;
dfs(x);
}