杭电 hdu 2544 最短路

这题是经典的 Dijkstra 解法的应用，当然，我一开始因为看不懂，所以按照动态规划的转移方程去自己做了个用时为O(n3)的程序（跟 Floyd 有点像）感觉 Dijkstra 的地位特殊，因此又试着按他的解法做一遍。

我发现网上很多代码都过不了我的一个合法测试数据。

后来，我对自己的代码进行修改，使其能支持某些非法数据。具体的情况我已经有很多注释了。请看代码吧。

我自己的代码：

// 我自己的代码，跟 Floyd 有点像。。。。。
/* THE ROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//

        URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2544
        Name  : 最短路

        Date  : 2011/4/5 Tuesday
        Begin :
        End   :

        Result:
00733118	2011-04-04 21:53:06 	Accepted	1001	125 MS	424 KB	GNU C++		pyy
00733208 	2011-04-05 01:12:44 	Accepted 	1001 	46  MS 	368 KB Visual C++ 	pyy


Test Data:
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

5 9
 1 2 5
 1 2 2
 1 3 2
 1 3 3
 1 4 3
 2 3 5
 2 5 6
 3 5 4
 4 5 9
// 6
// 1->3->2 的情况 , 很多人的代码都过不了这题
5 9
 1 2 5
 1 2 7
 1 3 2
 1 3 3
 1 4 3
 2 3 1
 2 5 1
 3 5 4
 4 5 9
// 4
// 1->3->4->2->5 的情况
 5 5
 1 2 10
 1 3 4
 2 4 2
 3 4 3
 2 5 5
// 14
// 1->3->4->2->5 的情况
 5 6
 1 2 10
 1 3 4
 2 4 2
 3 4 3
 2 5 5
 4 5 100
// 14
// 非法数据，终极数据
 2 4
 1 2 10
 1 3 4
 2 4 2
 3 4 3
// 9

//----------------------------------------------------------------------------*/

#include <iostream>
#include <string.h>
#define M 11111
#define M2 111

using namespace std;

inline int min( const int &lhs, const int &rhs )
{
        return ( lhs < rhs ) ? lhs : rhs;
}
int     p[M],           // 最短路径集
        map[M2][M2];    // 地图
int main()
{
        const int MAXIMUM = 0xfffffff;

        int i, j, k;

        int cross, street, a, b, cost, maxCross;
        while( cin >> cross >> street && cross && street )
        {
                // 初始化，p 和 map 所有路为不可通
                for( i = 0; i < M; i++ )
                        p[i] = MAXIMUM;
                for( i = 0; i < M2; i++ )
                        for( j = 0; j < M2; j++ )
                                map[i][j] = MAXIMUM;

                p[1] = 0;
		maxCross = 0;
                for( i = 1; i <= street; i++ )
                {
                        cin >> a >> b >> cost;
                        // 编号最大的路口。
			maxCross = ( maxCross < max(a,b) ) ? max(a,b) : maxCross;
			// 过滤出两点间的直接最短路径。
                        map[a][b] = map[b][a] = ( cost < map[a][b] ) ? cost : map[a][b];
                }

		/*------------------------------------------------------------//
		第一层循环的意义（最外层）：由于1到节点2的最短路径，有可能要经
		过3或4或其他任何比2大的节点.
		第二层循环其实是从1到某个节点的临时最短路，
		假如1到2的最短路是1->3->2, 那么当循环到2时，因为3->2的路径要涉
		及到第3个节点，而这条路还没有出来，所以这时3->2的路径是无穷大
		的，
		即：p[2]=min(p[2],p[3]+map[3][2])
		p[3]+map[3][2]为无穷大，而p[2]为有限小，所以自然选p[2]。
		只有当第二层循环完毕之后，p[3]才为有限小，所以要有最外层循环。
		//------------------------------------------------------------*/
                for( i = 1; i <= maxCross; i++)
                        for( j = 1; j <= maxCross; j++ )
                        {
                                for( k = 1; k <= maxCross; k++ )
                                        p[j] = min( p[j], p[k] + map[k][j] );
                        }
                cout << p[cross] << endl;
        }

        return 0;
}

Dijkstra 解法：

// Dijkstra 解法

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

        URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2544
        Name  : 最短路

        Date  : 2011/4/5 Tuesday
        Begin :
        End   :

        Result:
00733219 2011-04-05 02:30:21 Accepted 1001 31 MS 308 KB Visual C++ pyy 

Test Data:
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

5 9
 1 2 5
 1 2 2
 1 3 2
 1 3 3
 1 4 3
 2 3 5
 2 5 6
 3 5 4
 4 5 9
// 6
// 1->3->2 的情况, 很多人的代码都过不了这题
5 9
 1 2 5
 1 2 7
 1 3 2
 1 3 3
 1 4 3
 2 3 1
 2 5 1
 3 5 4
 4 5 9
// 4
// 1->3->4->2->5 的情况
 5 5
 1 2 10
 1 3 4
 2 4 2
 3 4 3
 2 5 5
// 14
// 1->3->4->2->5 的情况
 5 6
 1 2 10
 1 3 4
 2 4 2
 3 4 3
 2 5 5
 4 5 100
// 14
// 非法数据，终极数据
 2 4
 1 2 10
 1 3 4
 2 4 2
 3 4 3
// 9

//----------------------------------------------------------------------------*/

#include <iostream>
#define MAX_CROSS 101
#define MAX_STREET 10001

using namespace std;

const int maxint = 0x0fffffff;

int main()
{
        bool flag[MAX_CROSS];
        int map[MAX_CROSS][MAX_CROSS], dist[MAX_CROSS];

        int i, j, k;
        int cross, street, a, b, cost, min_street, maxNode;

        while( cin >> cross >> street && cross && street )
        {
                // 对数组初始化: 所有路径都是不可通的
                for( i = 0; i < MAX_CROSS; i++ )
                        for( j = 0; j < MAX_CROSS; j++ )
                                map[i][j] = maxint;

                maxNode = 0;
                for( i = 1; i <= street; i++ )
                {
                        cin >> a >> b >> cost;
                        maxNode = ( maxNode < max( a, b ) ) ? max(a, b) : maxNode;
                        // 1. 这是个无向图; 2. 筛选两点间最短值.
                        map[a][b] = map[b][a] = ( cost < map[a][b] ) ? cost : map[a][b];
                }

                for( i = 1; i <= maxNode; i++ )
                {
                        dist[i] = map[1][i];            // 对最短路集合dist 初始化.
                        flag[i] = true;                 // "true" 表示它需要寻找一个最短路, "false" 表示它已经是最短路了
                }

                flag[1] = false;                        // "1" 到"1" 的最短路为0，不需要最短路了
                for( i = 2; i <= maxNode; i++ )
                {
                        min_street = maxint;            // "1" 到所有可通路的最小路径
                        // 找最短路集中的最小值
                        for( j = 2; j <= maxNode; j++ )
                                if( flag[j] && dist[j] < min_street )
                                {
                                        k = j;
                                        min_street = dist[j];
                                }

                        // "1" 到外围第i-1 层的最短路径已找到, 或
                        // "1" 到第k 个节点的临时最短路径已找到
                        flag[k] = false;

                        // "1" 到第k 个节点再到第j 个节点的最短路径:
                        for( j = 2; j <= maxNode; j++ )
                        {
                                if( flag[j] && dist[k] + map[k][j] < dist[j] )
                                        dist[j] = dist[k] + map[k][j];
                        }
                }
                cout << dist[cross] << endl;
        }
        return 0;
}