当前位置: 代码迷 >> 综合 >> poj 2267 From Dusk till Dawn or: Vladimir the Vampire 最短路spfa
  详细解决方案

poj 2267 From Dusk till Dawn or: Vladimir the Vampire 最短路spfa

热度:32   发布时间:2024-01-19 06:26:57.0

题意:

有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;	
}