专栏首页算法修养HDU 5636 Shortest Path(Floyed,枚举)

HDU 5636 Shortest Path(Floyed,枚举)

Shortest Path

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1146 Accepted Submission(s): 358

Problem Description There is a path graph G=(V,E) with n vertices. Vertices are numbered from 1 to n and there is an edge with unit length between i and i+1 (1≤i

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
#define mod 1000000007
typedef long long int  LL;
int dp[10][10];
int n,m;
long long int s;
int main()
{
    int t;
    scanf("%d",&t);
    int a[10];
    int x,y;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6]);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=6;i++)
        {
            for(int j=1;j<=6;j++)
            {
               dp[i][j]=abs(a[j]-a[i]);
            }
        }
        dp[1][2]=1;dp[3][4]=1;dp[5][6]=1;
        dp[2][1]=1;dp[4][3]=1;dp[6][5]=1;
        for(int k=1;k<=6;k++)
        {
            for(int i=1;i<=6;i++)
            {
                for(int j=1;j<=6;j++)
                {
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
                }
            }
        }
        int res=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            int ans=abs(y-x);
            for(int i=1;i<=6;i++)
            {
                for(int j=1;j<=6;j++)
                {
                    ans=min(ans,abs(x-a[i])+abs(y-a[j])+dp[i][j]);

                }
            }
//            int num=i*ans%mod;
//            res+=num;
//            res%=mod;
            (res+=(LL)i*ans%mod)%=mod;

        }
        printf("%d\n",res);


    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 单调队列,单调栈总结

    最近几天接触了单调队列,还接触了单调栈,就总结一下。 其实单调队列,和单调栈都是差不多的数据类型,顾名思义就是在栈和队列上加上单调,单调递增或者单调递减。当...

    ShenduCC
  • LeetCode 139 Word Break

    ShenduCC
  • HDU-4539郑厂长系列故事——排兵布阵(状态压缩,动态规划)

    郑厂长系列故事——排兵布阵 Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65535/3276...

    ShenduCC
  • HDU-6249-Alice’s Stamps

    ACM模版 描述 ? 题解 DPDP 问题,设 dp[i][j]dp[i][j] 表示前 ii 个位置选取 jj 个区间的最优解。当然 ii 要加以处理,因为我...

    f_zyj
  • 04:围棋

    总时间限制: 1000ms内存限制: 65536kB描述围棋的棋盘上有19*19条线交织成的361个交点,黑棋和白棋可以下在交点上。我们称这些交点为“目”。 一...

    attack
  • P2331 [SCOI2005]最大子矩阵

    题目描述 这里有一个n*m的矩阵,请你选出其中k个子矩阵,使得这个k个子矩阵分值之和最大。注意:选出的k个子矩阵不能相互重叠。 输入输出格式 输入格式: 第一行...

    attack
  • 87. [NOIP2000] 乘积最大

    ★☆   输入文件:cjzd.in   输出文件:cjzd.out 简单对比 时间限制:1 s   内存限制:128 MB   问题描述 今年是国际...

    attack
  • 【未完成】【leetcode第 165 场周赛】分割回文串 III

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • BUPT2017 wintertraining(15) #3 题解

    ​ 有n张牌,两人都可以从中拿出任意张,各自的得分为他们手中牌上的数字的异或和。求A的得分小于等于B的方案数。

    饶文津
  • 最快最简单的排序---桶排序

    是不是很好理解,就是开一个比最大数据大或者等于的一个数组,然后相应的桶遇到数就++,最后输出就行了。

    用户7727433

扫码关注云+社区

领取腾讯云代金券