解题报告 P1266 速度限制

题目内容

给出一个 n 个点的有向图（无重边），每个边有一长度和通过限速，如果进入某边时没有限速则延续之前的速度。求从0到 D 耗时最短的路径

解题思路

既然此时到达某个节点的速度开始具有后效性，那么不妨将速度记入状态中。在 Dijkstra 中直接令 d_{i,j} 表示以速度 j 进入节点 i 时的最小时间花费。则进行转移时可同时进行转移。

注意的点：

• vis 数组也要开成 vis[i][j]，因为 j 具有后效性，要一并记录
• double 类型的数组可以使用 memset(d,127,sizeof d) 来进行极大值的初始化
• priority_queue 使用自定义类型时需提前定义小于号（默认为大根堆，为实现小根堆需要将小于号反着写）
• 类似于一些 dp 的输出方案，需要在 Dijkstra 转移时记录下上一状态，输出时直接递归输出即可

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>

struct edge
{
    int from,to,v,l;
    double t;
    edge(){}
    edge(int a,int b,int c,int d)
    {
        from=a;
        to=b;
        v=c;
        l=d;
        t=(v==0?-1e8:(double)l/(double)v);
    }
};

struct node
{
    double d;
    int now;
    int v;
    node(){}
    node(double dd,int nnow,int vv)
    {
        d=dd;
        now=nnow;
        v=vv;
    }
};

bool operator<(const node &a,const node &b)//重载一个假的小于号来实现小根堆
{
    return a.d>b.d;
}

//城市编号从0开始 
const int maxn=150+5;
std::vector<edge> G[maxn];
int n,m,t,from[maxn][505],fromv[maxn][505];
double d[maxn][505];
bool vis[maxn][505];

void add(int from,int to,int v,int l)
{...}

void dijkstra()
{
    std::priority_queue<node> q;
    memset(d,127,sizeof(d));
    d[0][70]=0;
    q.push(node(0,0,70));
    while (!q.empty())
    {
        int now=q.top().now,v=q.top().v;
        q.pop();
        if(!vis[now][v])
        {
            vis[now][v]=1;
            for(auto &e:G[now])
            {
                if(e.v)
                {
                    if(d[e.to][e.v]>d[now][v]+e.t)
                    {
                        d[e.to][e.v]=d[now][v]+e.t;
                        q.push(node(d[e.to][e.v],e.to,e.v));
                        from[e.to][e.v]=now;
                        fromv[e.to][e.v]=v;
                    }
                }
                else
                {
                    if(d[e.to][v]>d[now][v]+(double)e.l/(double)v)
                    {
                        d[e.to][v]=d[now][v]+(double)e.l/(double)v;
                        q.push(node(d[e.to][v],e.to,v));
                        from[e.to][v]=now;
                        fromv[e.to][v]=v;
                    }
                }
            }
        }
    }
    return;
}

void Find_way(int now,int v)
{
    if(now!=0)
        Find_way(from[now][v],fromv[now][v]);
    printf("%d ",now);
}

int main()
{
    ...//输入
    dijkstra();
    int ansv;
    double mint=1e9;
    for(int i=1;i<=500;i++)
        if(mint>d[t][i])
            ansv=i,mint=d[t][i];//寻找如何往回寻路
    Find_way(t,ansv);
    return 0;
}