`
txf2004
  • 浏览: 6854602 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

【最短路+三种解法】杭电 hdu 1690 Bus System

 
阅读更多

Floyd 算法

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

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1690
    Name  : 1690 Bus System

    Date  : Saturday, January 21, 2012
    Time Stage : 7 hours

    Result: 
5283668	2012-01-21 17:27:37	Accepted	1690
78MS	288K	2952 B
C++	pyy

Test Data :

Review :
一共WA25次，不仅题意坑爹，数据也很坑爹，总结，这是一个坑爹的世界……

本题的路径之和貌似是无限接近 0x7fff,ffff,ffff,ffff 的，所以无穷大已经不保险了，
直接 -1 才是正道啊！

感谢华神的指点！
//----------------------------------------------------------------------------*/

#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>

using namespace std ;

#define INF        (-1)
#define MAXN        102

typedef __int64    LL ;

#define min(x, y)    ((x) < (y) ? (x) : (y))
#define max(x, y)    ((x) > (y) ? (x) : (y))
#define MEM(a, v)    memset (a, v, sizeof (a))

bool    used[MAXN] ;

int        n, m ;
int        L[4], C[4], id[MAXN] ;
LL            map[MAXN][MAXN] ;

void floyd ()
{
    int i, j, k ;
    for (k = 1 ; k <= n ; ++k)
        for (i = 1 ; i <= n ; ++i)
            for (j = 1 ; j <= n ; ++j)
                if (map[i][k] != INF && map[k][j] != INF)
                {
                    if (map[i][j] == INF || map[i][j] > map[i][k] + map[k][j])
                        map[i][j] = map[i][k] + map[k][j] ;
                }
}

// 这个已经没用了
int getid (int x)
{
    int i ;
    for (i = 1 ; i <= n ; ++i)
        if (id[i] == x)
            return i ;
    return 0 ;
}

int getdist (int i, int j)
{
    int tmp = id[i] - id[j] ;
    if (tmp < 0)
        tmp = -tmp ;
    if (0 < tmp && tmp <= L[0])
        return C[0] ;
    if (L[0] < tmp && tmp <= L[1])
        return C[1] ;
    if (L[1] < tmp && tmp <= L[2])
        return C[2] ;
    if (L[2] < tmp && tmp <= L[3])
        return C[3] ;
    return INF ;
}

void makemap ()
{
    int i, j ;
    MEM (map, INF) ;
    for (i = 1 ; i <= n ; ++i)
    {
        for (j = i + 1 ; j <= n ; ++j)
        {
            map[i][j] = map[j][i] = getdist (i, j) ;
        }
    }
}

int main ()
{
    int i, j, k ;
    int x, y, tcase ;
    LL ret ;

    scanf ("%d", &tcase) ;
    {
        k = 0 ;
        while (k++ < tcase)
        {
            for (i = 0 ; i < 4 ; ++i)
            {
                scanf ("%d", &L[i]) ;
            }
            for (i = 0 ; i < 4 ; ++i)
            {
                scanf ("%d", &C[i]) ;
            }

            scanf ("%d%d", &n, &m) ;

            for (i = 1 ; i <= n ; ++i)
            {
                scanf ("%d", &id[i]) ;
            }

            makemap () ;

            floyd () ;

            printf ("Case %d:\n", k) ;
            for (i = 0 ; i < m ; ++i)
            {
				// 这里输入的数字，直接就是下标了，不用 getid() 了
				// 一直以为 x,y 有可能是 -10000…… 到 10000……
                scanf ("%d%d", &x, &y) ;

                ret = map[x][y] ;

                if (ret == INF)
                    printf ("Station %d and station %d are not attainable.\n",
                    x, y) ;
                else
                    printf (
                    "The minimum cost between station %d and station %d is %I64d.\n",
                    x, y, ret) ;
            }
        }
    }
    return 0 ;
}


Spfa 算法

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

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1690
    Name  : 1690 Bus System

    Date  : Saturday, January 21, 2012
    Time Stage : 7 hours

    Result: 

5283757	2012-01-21 18:08:50	Accepted	1690
234MS	304K	3430 B
C++	pyy


Test Data :

Review :
本题的路径之和貌似是无限接近 0x7fff,ffff,ffff,ffff 的，所以无穷大已经不保险了，
直接 -1 才是正道啊！

感谢华神的指点！
//----------------------------------------------------------------------------*/

#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>

using namespace std ;

#define INF        (-1)
#define MAXN        102

typedef __int64    LL ;

#define min(x, y)    ((x) < (y) ? (x) : (y))
#define max(x, y)    ((x) > (y) ? (x) : (y))
#define MEM(a, v)    memset (a, v, sizeof (a))

bool		used[MAXN] ;

int			n, m ;
int			L[4], C[4], id[MAXN] ;
LL			dist[MAXN], map[MAXN][MAXN] ;

LL spfa (const int beg, const int end)
{
	int i, t ;

	queue<int>	q ;

	MEM (used, 0) ;
	MEM (dist, INF) ;
	
	q.push (beg) ;
	used[beg] = 1 ;
	dist[beg] = 0 ;

	while (!q.empty ())
	{
		t = q.front () ;
		q.pop () ;

		for (i = 1 ; i <= n ; ++i)
		{
			if (dist[t] == INF || map[t][i] == INF)
				continue ;
			if (dist[i] == INF || dist[i] > dist[t] + map[t][i])
			{
				dist[i] = dist[t] + map[t][i] ;
				if (!used[i])
				{
					used[i] = 1 ;
					q.push (i) ;
				}
			}
		}
		used[t] = 0 ;
	}

	return dist[end] ;
}

// 这个已经没用了
int getid (int x)
{
    int i ;
    for (i = 1 ; i <= n ; ++i)
        if (id[i] == x)
            return i ;
    return 0 ;
}

int getdist (int i, int j)
{
    int tmp = id[i] - id[j] ;
    if (tmp < 0)
        tmp = -tmp ;
    if (0 < tmp && tmp <= L[0])
        return C[0] ;
    if (L[0] < tmp && tmp <= L[1])
        return C[1] ;
    if (L[1] < tmp && tmp <= L[2])
        return C[2] ;
    if (L[2] < tmp && tmp <= L[3])
        return C[3] ;
    return INF ;
}

void makemap ()
{
    int i, j ;
    MEM (map, INF) ;
    for (i = 1 ; i <= n ; ++i)
    {
        for (j = i + 1 ; j <= n ; ++j)
        {
            map[i][j] = map[j][i] = getdist (i, j) ;
        }
    }
}

int main ()
{
    int i, k ;
    int x, y, tcase ;
    LL ret ;

    scanf ("%d", &tcase) ;
    {
        k = 0 ;
        while (k++ < tcase)
        {
            for (i = 0 ; i < 4 ; ++i)
            {
                scanf ("%d", &L[i]) ;
            }
            for (i = 0 ; i < 4 ; ++i)
            {
                scanf ("%d", &C[i]) ;
            }

            scanf ("%d%d", &n, &m) ;

            for (i = 1 ; i <= n ; ++i)
            {
                scanf ("%d", &id[i]) ;
            }

            makemap () ;

            printf ("Case %d:\n", k) ;
            for (i = 0 ; i < m ; ++i)
            {
				// 这里输入的数字，直接就是下标了，不用 getid() 了
				// 一直以为 x,y 有可能是 -10000…… 到 10000……
                scanf ("%d%d", &x, &y) ;

                ret = spfa (x, y) ;

                if (ret == INF)
                    printf ("Station %d and station %d are not attainable.\n",
                    x, y) ;
                else
                    printf (
                    "The minimum cost between station %d and station %d is %I64d.\n",
                    x, y, ret) ;
            }
        }
    }
    return 0 ;
}


Dijkstra 算法

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

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1690
    Name  : 1690 Bus System

    Date  : Saturday, January 21, 2012
    Time Stage : 7 hours

    Result: 

5283728	2012-01-21 17:54:39	Accepted	1690
468MS	292K	3628 B
C++	pyy


Test Data :

Review :
因为一张图要反复利用，所以 Floyd 会比 Dijkstra 快

本题的路径之和貌似是无限接近 0x7fff,ffff,ffff,ffff 的，所以无穷大已经不保险了，
直接 -1 才是正道啊！

感谢华神的指点！
//----------------------------------------------------------------------------*/

#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>

using namespace std ;

#define INF        (-1)
#define MAXN        102

typedef __int64    LL ;

#define min(x, y)    ((x) < (y) ? (x) : (y))
#define max(x, y)    ((x) > (y) ? (x) : (y))
#define MEM(a, v)    memset (a, v, sizeof (a))

bool    used[MAXN] ;

int        n, m ;
int        L[4], C[4], id[MAXN] ;
LL         dist[MAXN], map[MAXN][MAXN] ;

LL dijkstra (const int beg, const int end)
{
	int i, j ;
	int iMinPath ;
	LL MinPath ;

	MEM (used, 0) ;

	for (i = 1 ; i <= n ; ++i)
		dist[i] = map[beg][i] ;

	for (i = 1 ; i <= n ; ++i)
	{
		iMinPath = 0 ;
		MinPath = INF ;
		for (j = 1 ; j <= n ; ++j)
		{
			if (used[j] || dist[j] == INF)
				continue ;
			if (MinPath == INF || dist[j] < MinPath)
			{
				iMinPath = j ;
				MinPath = dist[j] ;
			}
		}
		used[iMinPath] = 1 ;
		for (j = 1 ; j <= n ; ++j)
		{
			if (used[j])
				continue ;
			if (dist[iMinPath] == INF || map[iMinPath][j] == INF)
				continue ;
			if (dist[j] == INF || dist[iMinPath] + map[iMinPath][j] < dist[j])
				dist[j] = dist[iMinPath] + map[iMinPath][j] ;
		}
	}
	return dist[end] ;
}

// 这个已经没用了
int getid (int x)
{
    int i ;
    for (i = 1 ; i <= n ; ++i)
        if (id[i] == x)
            return i ;
    return 0 ;
}

int getdist (int i, int j)
{
    int tmp = id[i] - id[j] ;
    if (tmp < 0)
        tmp = -tmp ;
    if (0 < tmp && tmp <= L[0])
        return C[0] ;
    if (L[0] < tmp && tmp <= L[1])
        return C[1] ;
    if (L[1] < tmp && tmp <= L[2])
        return C[2] ;
    if (L[2] < tmp && tmp <= L[3])
        return C[3] ;
    return INF ;
}

void makemap ()
{
    int i, j ;
    MEM (map, INF) ;
    for (i = 1 ; i <= n ; ++i)
    {
        for (j = i + 1 ; j <= n ; ++j)
        {
            map[i][j] = map[j][i] = getdist (i, j) ;
        }
    }
}

int main ()
{
    int i, k ;
    int x, y, tcase ;
    LL ret ;

    scanf ("%d", &tcase) ;
    {
        k = 0 ;
        while (k++ < tcase)
        {
            for (i = 0 ; i < 4 ; ++i)
            {
                scanf ("%d", &L[i]) ;
            }
            for (i = 0 ; i < 4 ; ++i)
            {
                scanf ("%d", &C[i]) ;
            }

            scanf ("%d%d", &n, &m) ;

            for (i = 1 ; i <= n ; ++i)
            {
                scanf ("%d", &id[i]) ;
            }

            makemap () ;

            printf ("Case %d:\n", k) ;
            for (i = 0 ; i < m ; ++i)
            {
				// 这里输入的数字，直接就是下标了，不用 getid() 了
				// 一直以为 x,y 有可能是 -10000…… 到 10000……
                scanf ("%d%d", &x, &y) ;

                ret = dijkstra (x, y) ;

                if (ret == INF)
                    printf ("Station %d and station %d are not attainable.\n",
                    x, y) ;
                else
                    printf (
                    "The minimum cost between station %d and station %d is %I64d.\n",
                    x, y, ret) ;
            }
        }
    }
    return 0 ;
}


分享到：
| 怎样做情人节巧克力？
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics