P7271 Speed Limits

· · 题解

个人建议评绿或蓝。

类似分层图的思想。

题意

说得很清楚，一张有向图，边权由其长度 L 速度 V 决定，如果未提供速度，那么就沿用走到这里的上一条边的速度，即 V_{old}。求单源最短路。

很容易发现，仅使用一维数组 dis[N] 是无法体现对速度的处理的。解释：假设你可以花 5 秒走到一个节点，速度为 1，而此时到下一个节点的边没有提供速度，所以你需要沿用 V=1，到达下一个点的时间较慢；同时你可以花 10 秒走到这里，这条路线速度为 8，只用花较短的时间就到达下一个节点。

所以，定义 dis[N][V] 表示以速度 v 到达 n 号节点的最短时间。

在最短路算法中，对于每一条边：当它速度不明时，沿用速度 V_{old} 计算边权，尝试更新 dis[to][v_old]；否则尝试更新 dis[to][v]。另外，不建议使用 SPFA。

if(e[i].v==0){ // 这条边速度不明
// 沿用v__old，更新dis[to][v_old]
}else{
// 更新 dis[to][v]
}

由于最终要求输出路径，所以我们在更新最短路的同时记录这个点是由哪个点走过来的，因为要考虑速度，所以为它多开一维。

pair<int, int> pre[155][505] // 两个维度分别是 *点编号* 和 *速度*
pre[to][e[i].v]=make_pair(temp.id, temp.speed); // 由旧点更新到新点

怎么找路径呢？ 我做的时候在这里卡了

首先，确定到达终点最优的状态，循环找出时间最短的速度，即找到使 dis[D][i] 最小的 i。然后再根据 pre 中的记录往后退，直到退回 0 号节点，途中再用数组记录路径（会光标倒退的可以直接输出）。

  int path[505], dx=0, w=0;
    for(int i=1;i<=500;i++){
        if(dis[t][i]<dis[t][w]) w=i;
    } // 找时间最小的状态，记录为 [t][w]
    for(int walker=t, sp=w;walker!=0;){ // 于是从 pre[t][w]开始退
        path[++dx]=walker;
        pair<int, int>g=pre[walker][sp];
        walker=g.first, sp=g.second;
    }
    cout << "0 ";
    for(;dx>0;dx--){ // 倒序输出
        cout << path[dx] << " ";
    }

完整版

#include "iostream"
#include "cstring"
#include "queue"
using namespace std;
int head[155], idx, n, m, t;
pair<int, int> pre[155][505];
int temp1, temp2, temp3, temp4;
double dis[155][505];
struct edge{
    int to, nxt, l, v;
}e[31250];
struct point{
    double d;
    int id, speed;
    point(double d, int id, int speed){
        this->d=d;
        this->id=id;
        this->speed=speed;
    }
    friend bool operator <(point p1, point p2){
        return p1.d > p2.d;
    }
};
void add_edge(int u, int v, int _v, int l){
    e[++idx].to=v;
    e[idx].l=l;
    e[idx].v=_v;
    e[idx].nxt=head[u];
    head[u]=idx;
}
void dijkstra(){ // 差不多是模板了
    memset(dis, 127, sizeof(dis));
    priority_queue<point>q;
    q.push(point(0, 0, 70)); // 点结构体：距离、编号、速度
    while(!q.empty()){
        point temp=q.top();
        q.pop();
        if(temp.d > dis[temp.id][temp.speed]) continue;
        dis[temp.id][temp.speed]=temp.d;
        for(int i=head[temp.id];i;i=e[i].nxt){
            int to=e[i].to;
            if(e[i].v==0){ // 速度不明，沿用旧速度
                double nd=temp.d+e[i].l*1.0/temp.speed;
                if(dis[to][temp.speed]>nd){
                    dis[to][temp.speed]=nd;
                    pre[to][temp.speed]=make_pair(temp.id, temp.speed);
                    q.push(point(nd, to, temp.speed));
                }
            }else{ // 自带速度，正常尝试更新
                double nd=temp.d+e[i].l*1.0/e[i].v;
                if(dis[to][e[i].v]>nd){
                    dis[to][e[i].v]=nd;
                    pre[to][e[i].v]=make_pair(temp.id, temp.speed);
                    q.push(point(nd, to, e[i].v));
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> t;
    for(int i=1;i<=m;i++){
        cin >> temp1 >> temp2 >> temp3 >> temp4;
        add_edge(temp1, temp2, temp3, temp4);
    }
    dijkstra();
    int path[505], dx=0, w=0;
    for(int i=1;i<=500;i++){
        if(dis[t][i]<dis[t][w]) w=i;
    }
    for(int walker=t, sp=w;walker!=0;){
        path[++dx]=walker;
        pair<int, int>g=pre[walker][sp];
        walker=g.first, sp=g.second;
    }
    cout << "0 ";
    for(;dx>0;dx--){
        cout << path[dx] << " ";
    }
}

21 年发的题目了，24 年 10 月开始写这个题解的时候，提交仅 36，通过5。这道题是真的没人看啊