杭电 hdu 1548 A strange lift

好吧，一条小小的贪心搞了我一个半小时，主要是图没有制好，所以屡次WA。同时也没有考虑到 5 1 1 和 5 5 1的情况。两者要分别输出 0 和 -1.

/* THE ROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//

        URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1548
        Name  : A strange lift

        Date  : Saturday, April 16, 2011
        Time Stage : 20:06~21:27

        Result:
3829659 2011-04-16 21:26:13 Accepted 1548 46MS 448K 2913 B C++ pyy

Test Data:

Sample Input
5 1 5
3 3 1 2 5

5 1 1
3 3 1 2 5

5 5 1
3 3 1 2 5

0

Sample Output
3

0

-1


Summary:
此题实际上并不难，由于第一次做有向图，所以移动的方向没有注意到。导致屡次 WA。
就此次做题来说，关键的一点是制图。一定要注意有向图的制法跟无向图是不同的。
并且要重点检查图是否正确。
//----------------------------------------------------------------------------*/

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int maxSize = 202, infinite = 0x0f0f0f0f;
int floor, minTrip, start, end;
int map[maxSize][maxSize], dp[maxSize], jump[maxSize], mark[maxSize];

// 附加函数，用于临时查看数组
void out( int (*arr)[maxSize] )
{
        int i, j;
        for( i = 1; i <= floor; i++ )
        {
                for( j = 1; j <= floor; j++ )
                        cout << arr[i][j] << " ";
                cout << endl;
        }
}

void dijkstra()
{
        int i, j, k;
        if( start == end )
        {
                minTrip = 0;
                return ;
        }
        memset( mark, 0, sizeof( mark ) );
        for( i = 1; i <= floor; i++ )
                dp[i] = map[start][i];
        for( i = 1; i <= floor; i++ )
        {
                int minPath = infinite;
                int iminPath = 0;
                for( j = 1; j <= floor; j++ )
                        if( !mark[j] && dp[j] < minPath )
                        {
                                iminPath = j;
                                minPath = dp[j];
                        }
                mark[iminPath] = 1;
                for( j = 1; j <= floor; j++ )
                        if( !mark[j] && dp[iminPath] + map[iminPath][j] < dp[j] )
                                dp[j] = dp[iminPath] + map[iminPath][j];
        }
        // 若 dp[end] 的值仍为 infinite 则没有到 end 的路径
        if( infinite == dp[end] )
                minTrip = -1;
        else
                minTrip = dp[end];
}

int main()
{
        int i, j, k;
        while( cin >> floor && floor )
        {
                memset( map, infinite, sizeof( map ) );
                cin >> start >> end;
                for( i = 1; i <= floor; i++ )
                {
                        cin >> jump[i];
//                        cout << endl << i << " " << jump[i] + i << endl;
                        // 这是个有向图，注意 map[i][i+jump[i]] 和 map[i+jump[i]][i] 是不同的。
                        if( i + jump[i] <= floor )
                        {
                                map[i][i+jump[i]] = 1;
//                                printf("%d->%d/t", i, i+jump[i] );
                        }
                        if( i - jump[i] > 0 )
                        {
                                map[i][i-jump[i]] = 1;
//                                printf("%d->%d", i-jump[i], i );
                        }
//                        cout << endl;
                }
//                out( map );
                dijkstra();
                cout << minTrip << endl;
        }
        return 0;
}