杭电 hdu 2066 一个人的旅行

第二次

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
	Copyright (c) 2011 panyanyany All rights reserved.

	URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2066
	Name  : 2066 一个人的旅行

	Date  : Friday, August 19, 2011
	Time Stage : half an hour

	Result:
4453342	2011-08-19 20:45:07	Accepted	2066
31MS	4200K	2070 B
C++	pyy


	Test Data:


	Review:
一开始忘记注释掉 freopen 函数了，结果悲剧地wrong answer
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

#define infinity    0x7f7f7f7f
#define minus_inf    0x80808080

#define MAXSIZE 1009

int road, neigh, dest, cityNum, minTime ;
int map[MAXSIZE][MAXSIZE], dp[MAXSIZE], used[MAXSIZE], want[MAXSIZE] ;

void dijkstra ()
{
	int i, j ;
	int minPath, iminPath ;
	memset (used, 0, sizeof (used)) ;
//	memset (dp, infinity, sizeof (dp)) ;

	for (i = 1 ; i <= cityNum ; ++i)
		dp[i] = map[0][i] ;

	for (i = 1 ; i <= cityNum ; ++i)
	{
		minPath = infinity ;
		iminPath = 0 ;		// 这里不用也行，下面会给它赋值的
		for (j = 1 ; j <= cityNum ; ++j)
		{
			if (!used[j] && dp[j] < minPath)
			{
				iminPath = j ;
				minPath	 = dp[j] ;
			}
		}
		used[iminPath] = 1 ;
		for (j = 1 ; j <= cityNum ; ++j)
		{
			if (!used[j] && dp[iminPath] + map[iminPath][j] < dp[j])
				dp[j] = dp[iminPath] + map[iminPath][j] ;
		}
	}

	minTime = dp[want[1]] ;
	for (i = 2 ; i <= dest ; ++i)
		minTime = min (minTime, dp[want[i]]) ;
}

int main ()
{
//	freopen ("C:\\in.txt", "r", stdin) ;
	int i, j ;
	int a, b, c ;
	while (scanf ("%d%d%d", &road, &neigh, &dest) != EOF)
	{
		memset (map, infinity, sizeof (map)) ;
		cityNum = 0 ;
		for (i = 1 ; i <= road ; ++i)
		{
			scanf ("%d%d%d", &a, &b, &c) ;
			map[a][b] = map[b][a] = min (map[a][b], c) ;
			cityNum = max (cityNum, max (a, b)) ;
		}
		for (i = 1 ; i <= neigh ; ++i)
		{
			scanf ("%d", &a) ;
			map[0][a] = map[a][0] = 0 ;
		}
		for (i = 1 ; i <= dest ; ++i)
		{
			scanf ("%d", &want[i]) ;
		}
		dijkstra () ;

		printf ("%d\n", minTime) ;
	}
	return 0 ;
}

第一次

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

        URL   :
        Name  :

        Date  : 2011/4/15 Friday
        Time Stage :

        Result:
        00638009 2011-04-15 01:54:52 Accepted 1001 31 MS 4208 KB Visual C++ pyy

Test Data:
Sample Input
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10
Sample Output
9
//----------------------------------------------------------------------------*/
#include <iostream>
#include <string.h>
using namespace std;
const int infinite = 0x08080808, maxSize = 1002;
int roads, neighbors, want, cost, maxPoint, minTrip;
int dp[maxSize], map[maxSize][maxSize], wanted[maxSize], mark[maxSize];

void dynamicProgramming()
{
        int i, j, k, iminRoad = 0;
        int minRoad;
        memset( mark, 0, sizeof( mark ) );
        for( i = 1; i <= maxPoint; i++ )
                dp[i] = map[0][i];
        for( i = 1; i <= maxPoint; i++ )
        {
                minRoad = infinite;
                iminRoad = 0;
                // 找到所有到0 点的路径中最短的
                for( j = 1; j <= maxPoint; j++ )
                {
                        if( !mark[j] && dp[j] < minRoad )
                        {
                                iminRoad = j;
                                minRoad = dp[j];
                        }
                }
                mark[iminRoad] = 1;
                // 借助该最短路径，查找0 到其他点之间是否有最短路径
                for( j = 1; j <= maxPoint; j++ )
                {
                        if( !mark[j] && dp[iminRoad] + map[iminRoad][j] < dp[j] )
                        {
                                dp[j] = dp[iminRoad] + map[iminRoad][j];
                        }
                }
        }
        // 查找0 到wanted 里面所有元素的路径中的最短路径
        minTrip = dp[wanted[1]];
        for( i = 2; i <= wanted[0]; i++ )
                if( dp[wanted[i]] < minTrip )
                        minTrip = dp[wanted[i]];
}

int main()
{
        int i, j, k;
        while( cin >> roads >> neighbors >> want )
        {
                maxPoint = 0;
                memset( map, infinite, sizeof( map ) );
                for( i = 1; i <= roads; i++ )
                {
                        cin >> j >> k >> cost;
                        map[j][k] = map[k][j] = min( cost, map[k][j] );
                        maxPoint = max( maxPoint, max( j, k ) );
                }
                for( i = 1; i <= neighbors; i++ )
                {
                        cin >> j;
                        map[0][j] = map[j][0] = 0;
                }
                for( i = 1; i <= want; i++ )
                {
                        cin >> wanted[i];
                }
                wanted[0] = want;
                dynamicProgramming();
                cout << minTrip << endl;
        }
        return 0;
}