题意:
有n个城市,城市之间有m列火车,每列火车都有发车时间和行驶时间。吸血鬼先生要乘火车从a到b,可以经过一些中间车站。但是他只能在晚上6点到次日凌晨6点之间在火车上而且他中午12点要和1L血,现在问最少要多少L血。
思路:
以用的血为消耗用spfa求最短路。
代码:
//poj 2267
//sepNINE
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <cstdio>
using namespace std;
const int maxN=128;
const int maxM=1024;
int head[maxN];
int dis[maxN][32],inq[maxN][32];
int e,n;
struct Edge
{int v,next,st,t;
}edge[maxM];struct Node
{int u,time;
};
void spfa(int s)
{queue< Node > Q; int i,j;for(i=1;i<=n;++i) for(j=18;j<=30;++j)dis[i][j]=INT_MAX;memset(inq,0,sizeof(inq));for(j=18;j<=30;++j){inq[s][j]=1;dis[s][j]=0;Node x;x.u=s;x.time=j;Q.push(x);}while(!Q.empty()){Node x=Q.front();int u=x.u;int time=x.time;Q.pop();inq[u][time]=0; for(i=head[u];i!=-1;i=edge[i].next){int st=edge[i].st,t=edge[i].t,v=edge[i].v; if(time<=st){if(dis[u][time]<dis[v][st+t]){ dis[v][st+t]=dis[u][time];if(inq[v][st+t]==0){inq[v][st+t]=1;Node x;x.u=v;x.time=st+t;Q.push(x); } }}else{if(dis[u][time]+1<dis[v][st+t]){dis[v][st+t]=dis[u][time]+1;if(inq[v][st+t]==0){inq[v][st+t]=1;Node x;x.u=v;x.time=st+t;Q.push(x); } } }} } return ;
}int main()
{int cases,casesNum=0;scanf("%d",&cases);while(cases--){int M,x,y;string a,b;map< string,int > m;memset(head,-1,sizeof(head));scanf("%d",&M);n=0;e=0; while(M--){cin>>a>>b>>x>>y;if(m[a]==0)m[a]=++n;if(m[b]==0)m[b]=++n;if(x<=6)x+=24;if(!(x>=18&&x+y<=30))continue;int u=m[a],v=m[b];edge[e].v=v;edge[e].st=x;edge[e].t=y;edge[e].next=head[u];head[u]=e++;}cin>>a>>b;if(m[a]==0)m[a]=++n;if(m[b]==0)m[b]=++n;spfa(m[a]);printf("Test Case %d.\n",++casesNum);int j,ans=INT_MAX;for(j=18;j<=30;++j)ans=min(ans,dis[m[b]][j]);if(ans==INT_MAX)printf("There is no route Vladimir can take.\n"); elseprintf("Vladimir needs %d litre(s) of blood.\n",ans);}return 0;
}