M_sea

洛谷1266 速度限制
Luogu分析显然是最短路,但是加入了速度这个量。所以可以当做二维最短路。设$dis[i][j]$表示到$i$这个...
扫描右侧二维码阅读全文
21
2018/10

洛谷1266 速度限制

Luogu

分析

显然是最短路,但是加入了速度这个量。所以可以当做二维最短路。

设$dis[i][j]$表示到$i$这个点,速度为$j$的最短时间。

然后直接跑最短路即可。

注意到图中没有负权边,SPFA大概不会被卡。

然后还要输出路径,直接记录前置状态即可。最后递归输出。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

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

struct Edge { int v,speed,l,nxt; };
Edge e[25010];
int head[310],cnt=0;

inline void addEdge(int u,int v,int speed,int l) {
    e[++cnt].v=v; e[cnt].speed=speed; e[cnt].l=l;
    e[cnt].nxt=head[u]; head[u]=cnt;
}

struct node { int u,v; };
double dis[310][510];
int inq[310][510];
node pre[310][510];
int n,m,D;

inline void Print(int u,int v) {
    if (pre[u][v].u!=-1) Print(pre[u][v].u,pre[u][v].v);
    printf("%d ",u);
}

inline void SPFA() {
    queue<node> Q; Q.push((node){0,70});
    for (re int i=0;i<=n;i++)
        for (re int j=0;j<=500;j++)    
            dis[i][j]=2e9,pre[i][j].u=pre[i][j].v=-1;
    dis[0][70]=0; inq[0][70]=1;
    while (!Q.empty()) {
        node fr=Q.front(); Q.pop();
        int u=fr.u,uv=fr.v; inq[u][uv]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,q=e[i].speed,l=e[i].l;
            int vv=q?q:uv;
            if (dis[u][uv]+(double)l/vv<dis[v][vv]) {
                dis[v][vv]=dis[u][uv]+(double)l/vv;
                pre[v][vv].u=u,pre[v][vv].v=uv;
                if (!inq[v][vv]) {
                    Q.push((node){v,vv});
                    inq[v][vv]=1;
                }
            }
        }
    }
}

int main() {
    n=read(),m=read(),D=read();
    for (re int i=1;i<=m;i++) {
        int a=read(),b=read(),c=read(),d=read();
        addEdge(a,b,c,d);
    }
    SPFA();
    double Min=2147483647; int sk=0;
    for (re int i=0;i<=500;i++)
        if (dis[D][i]<Min) Min=dis[D][i],sk=i;
    Print(D,sk);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 52 PM

发表评论