题解：P3259 [JLOI2014] 路径规划

· · 题解

写在前面

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)。

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

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