HDU 1690 Bus System

题目大意:给出若干巴士不同价格的票的乘坐距离范围,现在有N个站点,有M次询问,查询任意两个站点的最小花费

解析:由于是多次查询不同站点的最小花费,所以用弗洛伊德求解 时间复杂度(O^3) 比较基础的弗洛伊德

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 1000000000000 typedef __int64 LL;
const int N = ; __int64 dis[N][N],place[N];
__int64 L1,L2,L3,L4,C1,C2,C3,C4;
int n,m; LL judge(LL x)
{
if(x < )
x *= -;
if(x > && 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=; k<=n; k++)
{
for(int i=; i<=n; i++)
{
for(int j=; 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 = ;
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=; i<=n; i++)
{
scanf("%I64d",&place[i]);
}
for(int i=; i<=n; i++)
{
for(int j=i+; 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=; 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 ;
}
上一篇:在Flex4中使用RemoteObjectAMF0来连接fluorine网关 转


下一篇:UnicodeDecodeError: 'utf8' codec can't decode byte 0xce in position 47: invalid continuation byte