`

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

最短路图论floyddijkstraspfa 
阅读更多

 

 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
踩
分享到：
| 【最短路+dijkstra+spfa】杭电 hdu 2722 He ...
评论
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刷题地图+精选详细笔记

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

    acm课件简单数学题（杭电）（HDU）

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

    ACM HDU 2000-2099 解题报告 杭电　ACM

    《ACM HDU 2000-2099 解题报告 杭电 ACM》是一份详尽的编程竞赛解题集，主要涵盖了杭电（Hangzhou Dianzi University）在线判题系统（HDU OJ）上的2000至2099号题目。这份解题报告是针对参与ACM/ICPC（国际大学生...

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