题解 P3259 【[JLOI2014]路径规划】

· · 题解

P3259 [JLOI2014]路径规划

这种题为什么做的人这么少？？？

我来贡献一发题解。

题目大意：

给定一个无向图，每条边有边权，有些点有点权，一些点是加油站。

求一条起点到终点的最短路，使经过有点权的点不超过k次，一管油只能走limit的时间，时间到了就只能到加油站花cost的时间加油。

解法

那个红绿灯的计算公式是\frac{red^2}{2\times(red+green)}。

然后把这个时间附加到节点的出边上。

然后，我们建立分层图：

第i层表示经过了i个红绿灯时，从源点到该点的最短路径长度。

如果没有油量限制，那么我们直接跑最短路就行了。

所以我们考虑如何去掉这个油量限制。

注意到加油站很少，于是我们枚举以每个加油站为起点，向其他加油站经过若干个红绿灯的最短路径。

若此长度不大于最大油量，那么可以直接转移。

我们用这种方法构造新图，依旧是分层图，可是每一层仅有50个点，且没有油量限制。

然后就能跑分层图SPFA了。

注：不知道为什么，我的SPFA要加上SLF优化才能过，否则就是#4 TLE。

有空就到本蒟蒻的博客里坐坐嘛！

附代码：（我自己都觉得好丑啊。。。）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#include<string>
#include<deque>
#include<cmath>
#define MAXN 10010
#define MAXM 200010
#define eps (1e-7)
#define MAX (1<<30)//一大堆宏定义
using namespace std;

map<string,int> name;//直接用map存节点编号
int n,m,k,cost,limit,s,t;
int top=0,gas_stack[MAXN],id[MAXN][12];
double length[MAXN];
bool gas[MAXN];

inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}

struct SPFA{
    int c,head[MAXM];
    double path[MAXM];
    bool vis[MAXM];
    SPFA(){c=1;}
    struct Graph{
        int next,to;
        double w;
    }a[MAXM<<2];
    inline int relax(int u,int v,double w){
        if(path[v]>path[u]+w){
            path[v]=path[u]+w;
            return 1;
        }
        return 0;
    }
    inline void add(int u,int v,double w){
        a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
    }
    void spfa(int s){
        int u,v;
        deque<int> q;
        for(int i=1;i<=n*(k+1);i++){path[i]=MAX;vis[i]=false;}
        path[s]=0;
        vis[s]=true;
        q.push_back(s);
        while(!q.empty()){
            u=q.front();
            q.pop_front();
            vis[u]=false;
            for(int i=head[u];i;i=a[i].next){
                v=a[i].to;
                if(relax(u,v,a[i].w)&&!vis[v]){
                    vis[v]=true;
                    if(!q.empty()){
                        if(path[v]>path[q.front()])q.push_back(v);
                        else q.push_front(v);
                    }
                    else q.push_back(v);
                }
            }
        }
    }
}one,two;//旧图和新图

inline void add_edge(int u,int v,int w){//建立分层图
    if(fabs(length[v])>eps)for(int j=0;j<k;j++)one.add(id[u][j],id[v][j+1],w+length[v]);
    else for(int j=0;j<=k;j++)one.add(id[u][j],id[v][j],w);
}
void work(){//求解
    double ans=MAX;
    two.spfa(s);
    for(int i=0;i<=k;i++)ans=min(ans,two.path[t+i*n]);
    printf("%.3lf\n",ans);
}
void init(){//读入+预处理+建分层图
    string x;
    int u,v;
    double w;
    n=read();m=read();k=read();limit=read();cost=read();

    for(int i=0;i<=k;i++)
    for(int j=1;j<=n;j++)
    id[j][i]=j+i*n;

    for(int i=1;i<=n;i++){
        cin>>x;
        name[x]=i;
        int red=read(),green=read();
        if(x=="start")s=i;
        else if(x=="end")t=i;
        if(x.find("gas")!=string::npos)gas[i]=true;
        if(red)length[i]=1.00*red*red/(double)(2.00*(red+green));
        else length[i]=0;
    }

    for(int i=1;i<=m;i++){
        cin>>x;u=name[x];
        cin>>x;v=name[x];
        cin>>x;w=read();
        add_edge(u,v,w);
        add_edge(v,u,w);
    }

    gas[s]=gas[t]=true;
    for(int i=1;i<=n;i++)if(gas[i])gas_stack[++top]=i;

    for(int i=1;i<=top;i++){//旧图与新图的转换
        one.spfa(gas_stack[i]);
        for(int j=1;j<=top;j++){
            if(i==j)continue;
            w=(gas_stack[j]!=s&&gas_stack[j]!=t)?cost:0;
            for(int l=0;l<=k;l++)
            if(one.path[id[gas_stack[j]][l]]<=limit)
            for(int p=0;p+l<=k;p++)
            two.add(id[gas_stack[i]][p],id[gas_stack[j]][p+l],one.path[id[gas_stack[j]][l]]+w);
        }
    }
}
int main(){//主函数So easy!
    init();
    work();
    return 0;
}