题解：P3259 [JLOI2014] 路径规划

写在前面

将原图记作 $G_0$ ；
$dist_{i,x}$ 表示从当前起点出发，到达 $x$ ，经过 $i$ 个红绿灯，所需最小时间；
集合 $A=\{$ 所有加油站， $s$ ， $t\}$ 。

First

红灯的平均等待时间怎么求？

等待时间（平均）=总等待时间/总时间，也就是

\frac{a^2}{2(a+b)}

。

用下图思考会更易理解，总等待时间其实就是三角形面积。

Second

看到“最多经过

k

个红绿灯”，果断分层图 Dijkstra（SPFA）。

Third

注意到加油站的数量比较少，考虑从此下手，我们可以将加油站作为“中转点”，在原

G_0

上跑 Dijkstra（SPFA）。

Fourth

对于：任意

x,y\in A

，暴力求出

x

到达

y

的

dist_{i,y}(0\leq i\leq k,dist_{i,y} \leq Limit)

（跑 Dijkstra（SPFA）时，若

dist > Limit

，就 continue），再建一张图，记作

G_1

。

Fifth

最后只需以

s

为起点，在

G_1

上跑分层图即可。

Last：时间复杂度

以 Dijkstra 为例，设加油站的数量为

num

。

第一次 Dijkstra 的复杂度是

O(num\times K\times (n+m) \times \log n)

。

第二次 Dijkstra 的复杂度是

O(K^2\times num^2\times\log num)

（边数最多是

num^2\times K

）。

所以最终复杂度

O(num \times K\times m\times \log n + K^2\times num^2\times\log num)

。

最后的最后（~~这个才是你们要的~~）。

CPP

#include<bits/stdc++.h>
#define int long long
#define mp(x,y,p) make_pair(x,make_pair(y,p))
#define se second
#define fi first
using namespace std;
using PII=pair<int,int>;
using PDII=pair<double,PII>;
const int maxn=2e4+5;
const int maxm=4e5+5;
const double INF=1e18;
int n,m,K,Limit,Cost,s,t;
double Time[maxn];

unordered_map<string,int> Map;
vector<int> Gas;

struct Edge{int v,c,next; double w;};
struct Graph
{
	int head[maxn],tot;
	Edge e[maxm];
	double dist[15][maxn];
	bool vis[15][maxn];
	Graph()
	{
		memset(head,-1,sizeof(head));
		tot=-1;
	}
	void add(int u,int v,double w,int c)
	{
		e[++tot]=(Edge){v,c,head[u],w};
		head[u]=tot;
	}
	priority_queue<PDII,vector<PDII>,greater<PDII> >q;
	void init()
	{
		int i,j;
		for(i=0;i<=K+1;i++)
		{
			for(j=0;j<=n+1;j++)
			dist[i][j]=INF,vis[i][j]=0;
		}
	}
	void Dijkstra(int s)
	{
		int i; init();
		q.push(mp(0,0,s));
		dist[0][s]=0;
		while(q.size())
		{
			int k=q.top().se.fi,x=q.top().se.se;
			q.pop();
			if(vis[k][x])
			continue; 
			vis[k][x]=1;
			for(i=head[x];~i;i=e[i].next)
			{
				int y=e[i].v,c=e[i].c; double w=e[i].w;
				if(k+c<=K && dist[k+c][y]>dist[k][x]+w)
				{
					dist[k+c][y]=dist[k][x]+w;
					q.push(mp(dist[k+c][y],k+c,y));
				}
			}
		}
	}
}G[2];


bool Get_gas(string Name)
{
	for(int i=0;i+2<Name.size();i++)
	{
		if(Name[i]=='g' && Name[i+1]=='a' && Name[i+2]=='s')
		return true;
	}
	return false;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int i,k,x,y,u,v;
	double w; string Name;
	cin>>n>>m>>K>>Limit>>Cost;
	for(i=1;i<=n;i++)
	{
		cin>>Name>>x>>y;
		Map[Name]=i;
		if(x) Time[i]=1.0*x*x/(2*(x+y));
		if(Name=="start") Gas.push_back(s=i);
		if(Name=="end")   Gas.push_back(t=i);
		if(Get_gas(Name)) Gas.push_back(i);
	}
	for(i=1;i<=m;i++)
	{
		cin>>Name; u=Map[Name];
		cin>>Name; v=Map[Name];
		cin>>Name>>w;
		G[0].add(u,v,w+Time[v],(Time[v]? 1:0));
		G[0].add(v,u,w+Time[u],(Time[u]? 1:0));
	}
	for(int i:Gas)
	{
		G[0].Dijkstra(i);
		for(int j:Gas)
		{
			if(i==j) continue;
			for(k=0;k<=K;k++)
			{
				if(G[0].dist[k][j]>Limit) continue;
				w=((j!=s && j!=t)? Cost:0);
				G[1].add(i,j,G[0].dist[k][j]+w,k);
			}
		}
	}
	
	double ans=INF;
	G[1].Dijkstra(s);
	for(i=0;i<=K;i++)
	ans=min(ans,G[1].dist[i][t]);
	cout<<fixed<<setprecision(3)<<ans<<'\n';
	return 0;
}

题解：P3259 [JLOI2014] 路径规划

文章操作

写在前面

First

Second

Third

Fourth

Fifth

Last：时间复杂度

相关推荐

评论

题解：P3259 [JLOI2014] 路径规划