`

【最短路+三种解法】杭电 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 ;
}

 

0
0
分享到:
评论
1 楼 wshcdr 2012-01-22  
kan kan

相关推荐

    杭电HDU ACM培训课件

    《杭电HDU ACM培训课件》是一份珍贵的学习资源,源自杭州电子科技大学的ACM竞赛培训课程。这些课件是官方论坛上分享的,旨在为那些积分不足无法获取资源或者对ACM编程竞赛感兴趣的初学者提供帮助。下面将详细阐述这...

    杭电HDU2050题的ac程序

    一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了

    计算机网络复习大纲_杭电hdu.pdf

    计算机网络复习大纲_杭电hdu.pdf

    计算机网络复习大纲_杭电hdu整理.pdf

    计算机网络复习大纲_杭电hdu整理.pdf

    计算机网络复习大纲_杭电hdu参考.pdf

    计算机网络复习大纲_杭电hdu参考.pdf

    杭电HDU ACM 1005

    杭电ACM1005题源代码,AC了的程序,无问题……

    杭电操作系统实验 HDU操作系统实验.zip

    杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    hdu_ACM.rar_ACM_hdu_hdu acm_hdu_ACM_杭电ACM

    杭电hdu acm资料所用杭电的acm题

    计算机网络复习大纲_杭电hdu借鉴.pdf

    物理层是网络的最底层,负责数据的物理传输,包括单工、半双工和全双工三种方式。模拟信号和数字信号是电信号的两种形式,模拟信号连续变化,数字信号以离散电平代表0和1。 总结以上,本复习大纲全面覆盖了计算机...

    HDU杭电 计算机网络实验报告

    这份"HDU杭电 计算机网络实验报告"压缩包提供了丰富的实验材料,涵盖了多个关键的网络技术,包括交换机配置、路由协议、地址转换(NAT)、访问控制列表(ACL)以及动态主机配置协议(DHCP)等。以下是这些实验报告所...

    HDU 杭电操作系统实验 (通过验收)

    包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...

    杭电(HDU)ACM题解

    HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字

    acm课件搜索(杭电)(HDU)

    "acm课件搜索(杭电)(HDU)"这个主题聚集了相关的学习材料,特别是针对搜索算法的讲解,旨在帮助学生快速掌握并应用这些技术。 搜索算法在ACM竞赛中扮演着至关重要的角色,常见的搜索策略包括深度优先搜索(DFS)...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU刷题地图+精选详细笔记

    本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!

    acm课件简单数学题(杭电)(HDU)

    在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC)中,数学是至关重要的一部分,尤其是在解决杭电(Hangzhou Dianzi University,简称HDU)的题目时。本课件"acm课件简单...

Global site tag (gtag.js) - Google Analytics