hdu 1690 Bus System(最短路)

問題：

鏈接：點擊打開鏈接

題意：

思路：

代碼：

#include 
#include 
#include 
using namespace std;
#define INF 1000000000000

typedef __int64 LL;
const int N = 110;

__int64 dis[N][N],place[N];
__int64 L1,L2,L3,L4,C1,C2,C3,C4;
int n,m;

LL judge(LL x)
{
    if(x < 0)
        x *= -1;
    if(x > 0 && x <= L1)
        return C1;
    else if(x > L1 && x <= L2)
        return C2;
    else if(x > L2 && x <= L3)
        return C3;
    else if(x > L3 && x <= L4)
        return C4;
    else
        return INF;
}

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

int main()
{
    //freopen("input.txt","r",stdin);
    int t;
    int kase = 1;
    cin>>t;
    while(t--)
    {
        scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d",&L1,&L2,&L3,&L4,&C1,&C2,&C3,&C4);
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%I64d",&place[i]);
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                __int64 x = place[i] - place[j];
                dis[i][j] = dis[j][i] = judge(x);
            }
        }
        floyd();
        printf("Case %d:\n",kase++);
        for(int i=1; i<=m; i++)
        {
            int st,ed;
            scanf("%d%d",&st,&ed);
            if(dis[st][ed] != INF)
                printf("The minimum cost between station %d and station %d is %I64d.\n",st,ed,dis[st][ed]);
            else
                printf("Station %d and station %d are not attainable.\n",st,ed);
        }
    }
    return 0;
}

收獲：

---------------------------------------------------------

戰斗，從不退縮；奮斗，永不停歇~~~~~~~~~~~~~~