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;

}