洛谷1266 速度限制

题意

给出一个 $N$ 点 $M$ 边的有向图，要从 $1\rightarrow D$ 。每条边上有限速，如果限速为 $0$ 则需要按照上一条边的速度走。求最短用时。

$N\le 150$ 。

题解

给朴素的最短路加上一维，用 $dis[x][s]$ 表示在节点 $x$ ，当前速度为 $s$ 的最短用时。然后跑 $\text{Spfa}$ 即可。

tips: 对 double 进行 memset 时最好选择 0x42

#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>

using namespace std;

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

struct Edge {
    int next,to,w,s;
} edge[22505];
const int N=155;
bool in[N][505];
pii pre[N][505];
double dis[N][505];
int cnt,head[N],n,m,a,b,c,d,D,out[N],ocnt;

inline void add(int u,int v,int w,int s)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].s=s;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void spfa()
{
    memset(dis,0x42,sizeof(dis));
    dis[1][70]=0;
    queue <pii> q;
    q.emplace(mp(1,70));
    while (!q.empty())
    {
        int x=q.front().first,sx=q.front().second; q.pop();
        in[x][sx]=0;
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,w=edge[i].w,sy=edge[i].s;
            if (!sy) sy=sx;
            if (dis[x][sx]+1.0*w/sy<dis[y][sy])
            {
                dis[y][sy]=dis[x][sx]+1.0*w/sy;
                pre[y][sy]=mp(x,sx);
                if (in[y][sy]) continue;
                in[y][sy]=1;
                q.emplace(mp(y,sy));
            }
        }
    }
}

signed main()
{
    n=read(); m=read(); D=read()+1;
    for (int i=1;i<=m;i++)
    {
        a=read()+1; b=read()+1; c=read(); d=read();
        add(a,b,d,c);
    }
    spfa();
    double mn=1e12; int last;
    for (int i=0;i<=500;i++)
    {
        if (dis[D][i]>=mn) continue;
        mn=dis[D][i];
        last=i;
    }
    out[++ocnt]=D;
    for (pii i=pre[D][last];i.first;i=pre[i.first][i.second]) out[++ocnt]=i.first;
    for (int i=ocnt;i;i--) printf("%d ",out[i]-1);
    return 0;
}