看到题解里没有链式前向星的堆优化$Dijkstra$,那我就来一发。

题目分析

首先是源点到一个终点的最值问题,很容易想到是单源最短路径,我采用的是$Dijkstra$算法。当然思路还是大同小异的,这篇文章仍有参考价值。

设计状态

你可能会问了:

这哪里是最短路啊?题目问的不是最短时间吗?

诶,这就是你的$naive$了。这里我们可以考虑不将状态设置为最短路径(当然,题目也没有最短路径这么一说),而是将状态设置为其它符合题意的东西。

例如题目中问的:$\text{print the shortest time}$ (打印最短时间),我们就把状态设置为最短时间。很明显,dis[i]表示的就是从起点到点i的最短时间。

可以很容易得总结出一个套路:一般的裸题如果问的是某某的最值,dis[i]一般就可以设计为起点到点i的最值。当然并不适用于所有题(因为有的题目不够裸

状态更新

你可能又会问了:

这路径的更新好难判断啊

诶,这就是你的$naive$了。其实一共只有$2$种情况:

  1. 没时间过去这条路。
  2. 有时间过去这条路。

首先是没时间过去这条路,那就是当前这条路的剩余开放时间大于通过这条路需要的时间

怎么求这个当前这条路的剩余开放时间大于通过这条路需要的时间呢?

假如把这条路开放的操作和关闭的操作看做一轮,那就可以以下两句话解释:

  1. 现在这轮过去了多久;
  2. 一轮的时间减去这轮过去了多久就是剩余开放时间了。

这轮过去了多久很好求,假如现在在结点$u$,要到结点$v$,那么dis[u]就是当前的时间。用当前的时间一轮的时间取模,不就是这轮过去了多久吗?

那么上面哪两种情况就非常好写了:

//先计算上面提到的量
int v = e[i].v;	//终点
int sum = e[i].close + e[i].open;	//一轮的时间
int cost = dis[u] % sum;
int spend;	//spend是储存通过这条路总共需要花费的时间

接下来是两种情况

//Case 1
//e[i].w是通过这条路需要的时间
if(cost + e[i].w > e[i].open) )
	spend = sum - cost + e[i].w;
	//第一种情况,这轮你过不去
	//那么你要先等sum-k的时间,在加上过去这条路的时间
//Case 2
else
	spend = e[i].w;
	//过的去,那就只需要过这条路的时间

到这里,就算分析完了。

代码示例

#include <cstdio>
#include <queue>
#include <utility>
#include <vector>
using std::priority_queue;
using std::pair;
using std::vector;
using std::make_pair;
using std::greater;
using std::less;

#define rint register int
#define inf 0x3f3f3f3f
#define pa pair<int,int>
const int maxn = 305;
const int maxm = 50005;
typedef long long ll;

struct edge{
	int v,nxt,w;
	int open,close;
} e[maxm];
int n,m,s,t,head[maxn],tot,dis[maxn],Orz;
bool conf[maxn];
priority_queue <pa,vector<pa>,greater<pa> > dij;

inline int read();
void add(int u,int v,int a,int b,int t){e[++tot].close=b;e[tot].open=a;e[tot].v=v;e[tot].w=t;e[tot].nxt=head[u];head[u]=tot;}

int main(){
	while(scanf("%d %d %d %d",&n,&m,&s,&t)!=EOF){++Orz;tot=0;
		for(rint i=1;i<=n;++i)
		head[i]=0;
		for(rint i=0;i<maxm;++i)
		e[i].v=e[i].nxt=e[i].w=e[i].open=e[i].close=0;
		for(rint i=1;i<=n;++i)dis[i]=inf,conf[i]=false;
		for(rint i=1;i<=m;++i){
			int a=read(),b=read(),c=read(),d=read(),e=read();
			if(c>=e)
			add(a,b,c,d,e);
		}
		dis[s]=0;
		dij.push(make_pair(0,s));
		while(dij.size()){
			int u = dij.top().second;dij.pop();
			if(conf[u])continue;
			conf[u]=true;
			for(rint i = head[u];i;i=e[i].nxt){
				int v = e[i].v;
				int sum = e[i].close + e[i].open;
				int k = dis[u]%sum;
				int spend = 0;
				if(k + e[i].w > e[i].open)spend = sum - k + e[i].w;
				else spend = e[i].w;
				spend += dis[u];
				if(dis[v] > spend){
					dis[v] = spend;
					dij.push(make_pair(dis[v],v));
				}
			}
		}
		while(dij.size())dij.pop();
		printf("Case %d: %d\n",Orz,dis[t]);
	}
    return 0;
}

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

熬夜写题解不容易(疯狂暗示

2 对 “题解 UVA12661 【有趣的赛车比赛 Funny Car Racing】”的想法;

    1. 这个是由Typecho数据库里的表直接倒腾过来的,可能该编辑器对Markdown的支持不好,排版问题已经出了好多问题了。。。
      凑合着看吧。
      感谢您的反馈。

发表评论

邮箱地址不会被公开。