同济大学ACM上的一道题目: 最优乘车
网址如下: http://acm.tongji.edu.cn/showproblem.php?problem_id=1189
我输入数据时运行正确,但提交时运行错误,肯定是有些地方没考虑到,以下是我的代码:
#include<queue>
#include<iostream>
using namespace std;
//本题的解法是画一棵树,1为树根,各路线上位于其右边的站点作为其儿子
//然后从这些儿子出发将所在路线上位于其右边站点作为1的孙子...
//直到N出现,当处理队列头元素时将其儿子全部进队(进过的除外)
int main()
{
char s[1024];//接收一条路线
int M;//总路线数
int N;//总车站数
int **pp;
int *p;
int *line;
queue<int>my_queue;
cin>>M>>N;
pp = new int*[M];//指针数组
line = new int[N+1];//line[k]代表从站点1到站点k途经的最少线路数
line[1] = 0;
for (int k = 2; k <= N; k++)
line[k] = INT_MAX; //初始化为最大值
//
//cin.clear();
cin.ignore(INT_MAX,'\n'); //将流清空,避免以下的输入受影响
for (int i = 0; i < M; i++)
{
cin.getline (s, 1024, '\n');
pp[i] = new int [501];//一条路线对应一个一维动态数组
p = pp[i];
int j = 0;
//存储路线中的车站编号进数组
while (s[j] != '\0')
{
int sum = 0;
//连接成为一个数字,即车站编号
while (s[j] != ' ' && s[j] != '\0')
{
sum *= 10;
sum += s[j] - '0';//从ASCII码转为数字
j++;
}
*p++ = sum;//存储编号
if (s[j] == ' ')
j++;//跳过空格
}
*p = -1;//置结束标志
}
//先将起点放入队列中
my_queue.push (1);
//遍历队列
while ( !my_queue.empty () )
{
int num = my_queue.front ();
my_queue.pop (); //队头出列
//遍历动态数组以便找出包含num的路线
for (int i = 0; i < M; i++)
{
p = pp[i];
while (*p != -1 && *p != num)
p++;
//找到了
if (*p == num)
{//将num右边的站点进队
while (*(++p) != -1)//-1为结束标志
{
int index = *p;
if (line[index] > line[num] + 1)//index表示的站点还没进过队列则进队
{
my_queue.push (index);
line[index] = line[num] + 1;//line[index]现已为换乘当前路线到index站点最佳的
//N已经出现了,所以最少路线数也就确定了
if (index == N)
{
cout<<(line[N]-1)<<endl;
//释放内存
delete [] line;
for (int j = 0; j < M; j++)
delete [] pp[j];//一维数组
delete [] pp;
return 0;
}
}
}
}//if (*p == num)
}
}//while
cout<<"NO"<<endl;
//释放内存
delete [] line;
for (int j = 0; j < M; j++)
delete [] pp[j];
delete [] pp;
return 0;
}
问题点数：30、回复次数：3Top
1 楼liking100（阿他）回复于 2006-06-03 20:51:44 得分 0
我也做过这道题的，不过我没有仔细考虑~呵呵
觉得LZ的想法不错，呵呵，继续努力Top
2 楼lcy3125891（）回复于 2006-06-04 00:09:23 得分 0
高手都去哪了?帮帮我啊!Top
3 楼cattlenzq（吃狼的豆腐（不要给分了，散起来真麻烦！））回复于 2006-06-04 00:33:08 得分 0
mark下，睡觉先Top
