时间就是金钱HNCOI2000
版权声明：本篇随笔版权归作者YJSheep(www.cnblogs.com/yangyaojia)所有，转载请保留原地址!
人们总是选时间最短或费用最低的路线
例如，
|
出发地 |
目的地 |
开始时间 |
到达时间 |
费用 |
|
A |
B |
5:20 |
6:55 |
12.50 |
|
A |
C |
5:45 |
9:15 |
35.00 |
|
B |
C |
7:45 |
9:35 |
20.00 |
如果我们将从A到C，我们可以选择两条路径。
1.A->B->C 2.A->C。
前者时间为4:15，费用为32.50，后者是时间3:30，费用为35.00。
现为了综合考虑时间和费用的问题，我们常采用单位时间相当于多少费用的方法，来选择最低的旅游路线。我们假设:
(1) 旅游时间为最后1辆车的到达时间和第1辆车的出发时间之差
(2) 一小时旅游时间相当于费用10.00
(3) 时间采用24小时，格式为:HH:MM
(4) 旅游开始和结束时无等待时间，只有在转车的时候才有等待时间。如果等待时间超过12小时，将会因为住宿和误餐而多花费费用30.00
(5) 一个地点到另一个地点的直接车次可能有多个。例如，A到B可能有:同一时间出发的2种以上的车次，或者不同时间的2种以上的车次
(6) 任何车次的车票都是可买到的，任何车次的最长运行时间<=24小时
任务:根据旅行车次时间表和出发地、目的地，根据以上原则，求出最小的旅游费用
输入:输入文件若干行，第1行为2个城市名，分别是出发地和目的地，以后每一行为1辆车次的5个数据，分别是出发地，目的地，开始时间，到点时间，费用。数据之间用空格分开。城市数<=30，车次数<=2000
输出:输出文件为1行，即最低费用(四舍五入精确到小数后2位)。
样例:
Input.txt
A C
A B 5:20 6:55 12.50
A C 5:45 9:15 35.00
B C 7:45 9:35 20.00
Output.txt
70.00
测试数据
Input1:
B A
B C 20:00 22:00 09.20
B C 13:00 14:10 20.34
C A 14:30 16:00 39.95
Output1:
90.29
Input2:
A C
A B 06:30 07:00 12.50
A C 05:45 09:15 55.00
B C 07:45 09:35 40.00
A D 06:30 07:30 30.00
D C 09:00 11:30 10.00
B D 07:00 08:00 10.00
Output2:
82.50
Txt.3即样例
解题报告
很老的题目，比较经典(笑)
在生活中，赶车是来的早不如来的巧。这题也是一样，你也许选择了一辆耗时较少的车，但因为出发的比较早，最后到的时间是一样的，结果耗时比出发时间晚的车多。所以，把车的一趟线路作为一条边是不妥的。不过，我们转眼一想，不妨把一趟车作为一个点，如果一趟车的终点是另一趟车的起点，就可以连一条有向路径。这条路径的权值为这趟车本身的花费加上等到下一趟车所需的花费。因为可能有许多点的出发点为起点，许多点的结束点为终点，我们不知道取哪一个起点还是终点。故我们可以加一个起点到起点的点作为起点，与终点到终点的点作为终点。起点所连的边权值都为0，连向终点的边没有等待时间，只有前一个点本身的花费，这样处理就会方便很多。 还有，其实这题最好“金钱就是时间” 吧所有花费转换为 分钟 来计量，这样精度会高一点。
不知道为什么有一个测试点过不了，希望帮忙找找错。
#include<queue> #include <algorithm> #include<cstdio> #include<cstring> #include<cmath> #define Pair pair<double,int> #define MAXN 2000+10 #define MAX 99999999 #define MAXM 600000+1 using namespace std; int n,m,num,nnum,head[MAXN],s,t,pre[MAXN],v[MAXN]; double dis[MAXN]; struct Node{ int from,to,st,tt;double dis; }node[MAXN]; struct Edge{ int next,to,exi,from; double dis,s,t,tim; }edge[MAXM]; void add(int from,int to,double dis) { edge[++num].next=head[from]; edge[num].to=to; edge[num].dis=dis; edge[num].from=from; head[from]=num; } double dist(int x,int y) { if(x==s) return 0; if(x==t) return MAX; if(y==t) return node[x].dis; int h=node[x].tt,g=node[y].st; // printf("%d %d %lf ",h,g,node[x].dis); if(g<h) g+=24*60; if(g-h>=12*60) return 3*60+(g-h)%(24*60)+node[x].dis; else return (g-h)%(24*60)+node[x].dis; } void dij() { for(int i=1;i<=nnum;i++) dis[i]=99999999; memset(pre,0,sizeof(pre)); memset(v,0,sizeof(v)); priority_queue<Pair,vector<Pair>,greater<Pair> > h; dis[s]=0; h.push(Pair(dis[s],s)); while(h.size()>0) { int k=h.top().second;h.pop(); if(v[k]) continue; v[k]=1; for(int i=head[k];i;i=edge[i].next) { if(dis[k]*1.0+edge[i].dis*1.0<dis[edge[i].to]) { dis[edge[i].to]=dis[k]*1.0+edge[i].dis*1.0; pre[edge[i].to]=edge[i].from; h.push(Pair(dis[edge[i].to],edge[i].to)); } } } } int main() { freopen("money.in","r",stdin); freopen("money.out","w",stdout); char ss[2],tt[2]; scanf("%s%s",ss,tt); s=ss[0]-'A'+1;t=tt[0]-'A'+1; while(scanf("%s%s",ss,tt)==2) { int x,y,sh,sm,th,tm,tim;double mon; scanf("%d:%d%d:%d%lf",&sh,&sm,&th,&tm,&mon); x=ss[0]-'A'+1;y=tt[0]-'A'+1;n=max(n,max(x,y)); if(th==0) th=24; sh=sh*60+sm;th=th*60+tm; printf("sh=%d th=%d ",sh,th); node[++nnum].st=sh;node[nnum].tt=th; if(sh>th) th+=60*24; tim=th-sh; printf("%d %d ",nnum,tim); node[nnum].from=x;node[nnum].to=y; node[nnum].dis=mon*6.0+tim*1.0; } node[++nnum].from=s;node[nnum].to=s; node[nnum].dis=0; s=nnum; node[++nnum].from=t;node[nnum].to=t; node[nnum].dis=MAX; t=nnum; for(int i=1;i<=nnum;i++) { for(int j=i+1;j<=nnum;j++) { if(node[i].to==node[j].from) add(i,j,dist(i,j)); else if(node[j].to==node[i].from) add(j,i,dist(j,i)); } } dij(); printf("%.2lf ",dis[t]/6.0); return 0; }