正文
POI0109 POD (最短路)
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
POI0109 POD (最短路)
版权声明:本篇随笔版权归作者YJSheep(www.cnblogs.com/yangyaojia)所有,转载请保留原地址!
现在让我们来对一个交通运输图进行研究,这可能是一个公交车的线路网、有轨电车线路网、地下铁的线路网或是其他的一个什么。这个图中的顶点(从1到n标号)为车站,边(p i ,p j )(这里p i ¹ p j )表示在顶点p i 和顶点p j 间存在一条直接连接两点的路(1 £ p i , p j £ n)。在图中有从1到k编号的k条运输路线,第l号路线是用一个车站序列p l,1 , p l,2 , …, p l,sl 来描述的,它们为使用这个线路的车辆将依次经过的车站。并且我们给出它们之间的距离r l,1 , r l,2 , …, r l,sl-1 ,其中r l,i 表示从车站p l,i 到车站p l,i+1 所需的时间。对于一条线路来说,它上面所有的车站都是不相同的(也就是说,若i ¹ j,则p l,i ¹ p l,j )。且线路l将以频率c l 运行。这里c l 为集合{6, 10, 12, 15, 20, 30 ,60}中的一个数,它表示每个小时的0, c l , 2c l , …, 60分钟的时候在路线l上的将有两辆车同时从车站p l,1 和p l,sl 出发相对着行进。
在这样一个运输网络中,我们想从其中的一个车站x出发用尽可能少的时间到达车站y。这里我们假设最少的时间不会超过24个小时,且在中途换车的时候的时间不计。
示例:
在下图中你可以看到一个具有六个车站和两条路线的运输网络。路线一上的车站序列为1、3、4、6,路线二上的车站序列为2、4、3、5,且两条路线的频率分别为c1=15和c2=20。车辆在各车站间移动时的耗费都分别用1和2的下标标在了图上。
现在我们假设在23点30分的时候我们在车站5想要到车站6去。我们必须等上10分钟才可以搭上一辆路线2的车离开。然后我们就面临着两种选择:一种是在23点51分到车站3等上3分钟并改乘路线1的车于0点16分到达车站6;另一种是在0点8分到达车站4等上13分钟再换路线1的车于0点31分到达车站6。显然最早我们能在0点16分到达车站6。
任务:
请写一个程序:
l 从文本文件POD.IN中读入对该交通运输网的描述、起点和终点、还有出发的时间;
l 找出从起点到终点的最少时间;
l 把最找到达终点的时间输出到文本文件POD.OUT中。
输入格式:
在文本文件POD.IN的第一行包括六个用空格分开的整数,分别为:
l n,1 £ n £ 1000,为车站的数目;
l k,1 £ k £ 2000,为路线的数目;
l x,1 £ x £ n,为起点的车站编号;
l y,1 £ y £ n,为终点的车站编号;
l g x ,0 £ g x £ 23,为出发时间的小时数;
l m x ,0 £ m x £ 59,为出发时间的分钟数。
车站是从1到n编号的,运输路线是用1到k编号的。以下的3k行为对运输路线的描述。这些行中每3行构成一个对一条路线的描述,第k个三行的意义如下:
l 第一行包括两个用空格分开的整数,s l (2 £ s l £ n)为该路线上车站的数目,还有c l ({6, 10, 12, 15, 20, 30, 60}中的一个元素),为该路线运行的频率;
l 第二行包括s l 个用空格分开的不同的整数,为p l,1 , p l,2 , …,p l,sl (1£ p l,i £ n),即该路线上的车站;
l 第三行包括s l -1个整数r l,1 , r l,2 , …,r l,sl-1 为在路线上相邻两个车站间移动所需的时间(1£ r l,i £ 240)。
在所有的运输路线上的总车站数不超过4000(也就是说s 1 + s 2 + … + s k £ 4000)。
输出格式:
你的程序应该在文本文件POD.OUT中输出两个整数g y (0£ g y £ 23)和m y (0£ m y £ 59),表示到达y点时的小时数和分钟数。
样例:
输入(POD.IN):
6 2 5 6 23 30
4 15
1 3 4 6
9 12 10
4 20
5 3 4 2
11 17 11
输出(POD.OUT):
0 16
解题报告
最短路中比较典型的模型的结合。对于每一条路线,我们把其站点上每一个点到其他点建立一条边,并记录发车频率于距离的前缀和,但要注意方向,如果为反方向就要用最后一个点的前缀和减去当前点的前缀和。
写一个等待函数,计算以当前状态(时间),如果要走当前的路要等待多久。在堆优dijkstra中加上一起松弛。复杂度为O(nlogn)
#include<bits/stdc++.h>
#define Pair pair<int,int>
#define MAXN 1000+10
#define MAXM 600000+1
using namespace std;
int n,m,num,head[MAXN],s,t,pre[MAXN],dis[MAXN],v[MAXM],hour,minute;
int s1[*MAXN][MAXN],s2[*MAXN][MAXN];
struct Edge{
int dis,next,to,exi,from,n,f;
}edge[MAXM];
void add(int from,int to,int dis,int exi,int n,int f)
{
edge[++num].next=head[from];
edge[num].to=to;
edge[num].f=f;
edge[num].dis=dis;
edge[num].from=from;
edge[num].n=n;
head[from]=num;
edge[num].exi=exi;
}
int read(){
int in=;
char ch=getchar();
for(;ch>''||ch<'';ch=getchar());
for(;ch>=''&&ch<='';ch=getchar()) in=in*+ch-'';
return in;
}
int wait(int dis,int x)
{
int minu=(dis-)%++;
if(edge[x].f==)
{
return (*edge[x].exi-((minu-(s2[edge[x].n][edge[x].from]%edge[x].exi))%edge[x].exi))%edge[x].exi;
for(int i=;i<=edge[x].exi;i++)
{
if((minu+i-(s2[edge[x].n][edge[x].from]%edge[x].exi))%edge[x].exi==)
return i;
}
}else
if(edge[x].f==)
{
int temp=s1[edge[x].n][s1[edge[x].n][]]-s2[edge[x].n][edge[x].from];
return (*edge[x].exi-(minu-(temp%edge[x].exi))%edge[x].exi)%edge[x].exi;
for(int i=;i<=edge[x].exi;i++)
if((minu+i-(temp%edge[x].exi))%edge[x].exi==) return i;
}
}
void dij()
{
memset(dis,,sizeof(dis));
memset(pre,,sizeof(pre));
memset(v,,sizeof(v));
priority_queue<Pair,vector<Pair>,greater<Pair> > h;
dis[s]=hour*+minute;
h.push(Pair(dis[s],s));
while(h.size()>)
{
int k=h.top().second;h.pop();
if(v[k]) continue;
v[k]=;
for(int i=head[k];i;i=edge[i].next)
{
int wa=wait(dis[k],i);
if(wa+dis[k]+edge[i].dis<dis[edge[i].to])
{
dis[edge[i].to]=dis[k]+edge[i].dis+wa;
pre[edge[i].to]=edge[i].from;
h.push(Pair(dis[edge[i].to],edge[i].to));
}
}
}
} int main()
{
freopen("pod.in","r",stdin);
freopen("pod.out","w",stdout);
n=read();m=read();s=read();t=read();hour=read();minute=read(); for(int i=;i<=m;i++)
{
int c=,sn=,l[MAXN];
memset(l,,sizeof(l));
sn=read();c=read();
s1[i][]=sn;
for(int j=;j<=sn;j++) l[j]=read();
for(int j=;j<=sn;j++)
s1[i][j]=read(),s1[i][j]+=s1[i][j-],s2[i][ l[j] ]=s1[i][j];
for(int j=;j<=sn;j++)
for(int h=j+;h<=sn;h++)
add(l[j],l[h],int(abs(s1[i][j]-s1[i][h])),c,i,),
add(l[h],l[j],int(abs(s1[i][j]-s1[i][h])),c,i,);
}
dij();
printf("%d %d\n",(dis[t]/)%,dis[t]%);
return ;
}
//6 10 12 15 18 24 30 36 40 42 45 48 50 54 60