时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：5153

解决：3298

题目描述：

    对于一个数n，如果是偶数，就把n砍掉一半；如果是奇数，把n变成 3*n+ 1后砍掉一半，直到该数变为1为止。
    请计算需要经过几步才能将n变到1，具体可见样例。

输入：

    测试包含多个用例，每个用例包含一个整数n,当n为0 时表示输入结束。（1<=n<=10000）

输出：

    对于每组测试用例请输出一个数，表示需要经过的步数,每组输出占一行。

样例输入：

3

1

0

样例输出：

5

0

来源：

2009年浙江大学计算机及软件工程研究生机试真题

 #include <cstdio>

 #include<algorithm>

 #include<iostream>

 #include<string>

 #include<cstring>

 #include<vector>

 using namespace std;

 struct point{

     int dis,cost;

 };

 point p[];

 int map[][][];

 #define inf 999999999

 int main(){

     //freopen("D://INPUT.txt","r",stdin);

     int n,m;

     while(cin>>n>>m&&n&&m){

     int i=,j;

     for(i=;i<=n;i++){

         for(j=;j<=n;j++){

             map[i][j][]=inf;

             map[i][j][]=inf;

         }

     }

     i=;

     for(;i<m;i++){

         int a,b;

         cin>>a>>b;

         cin>>map[b][a][]>>map[b][a][];

         map[a][b][]=map[b][a][];

         map[a][b][]=map[b][a][];

     }

     int s,e;

     cin>>s>>e;

     //cout<<s<<e<<endl;

     p[s].cost=;

     p[s].dis=;

     i=;

     for(;i<=n;i++){

         if(i==s)

         continue;

         p[i].dis=map[s][i][];

         p[i].cost=map[s][i][];

     }

     i=;

     for(;i<n;i++){

         int j,min=inf,k;

         for(j=;j<=n;j++){

             if(p[j].dis&&p[j].dis<min){

                 min=p[j].dis;

                 k=j;

             }

         }

         if(k==e){

             break;

         }

         for(j=;j<=n;j++){

             if(p[j].dis>p[k].dis+map[k][j][]){

                 p[j].dis=p[k].dis+map[k][j][];

                 p[j].cost=p[k].cost+map[k][j][];

             }

             else{

                 if(p[j].dis==p[k].dis+map[k][j][]){

                     p[j].cost=p[k].cost+map[k][j][]>p[j].cost?p[j].cost:p[k].cost+map[k][j][];

                 }

             }

         }

         p[k].dis=;

     }

     cout<<p[e].dis<<' '<<p[e].cost<<endl;

     }

     return ;

 }

 /**************************************************************

     Problem: 1008

     User: Deribs4

     Language: C++

     Result: Accepted

     Time:20 ms

     Memory:9416 kb

 ****************************************************************/