AT_abc192_e 题解

xuchuhan · 2024-01-31 23:12:13 · 题解

前言

赛时用了 SPFA 求最短路。结果，关于 SPFA，他死了。

思路

就是最短路板子，只是松弛操作有些变化。

最短路模板的松弛操作如下：dis_v=dis_u+w_{u,v}。其中 w_{u,v} 表示 u \rightarrow v 的边的长度。

而这道题的松弛操作即为：dis_v=dis_u+w_{u,v}+W(u,k)。其中 W(u,k) 表示当到达 u 点时，当前列车在时间为 k 的倍数时发车，还需要在站台等待多久。

其余就是，最好别用 SPFA。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,m,X,Y;
struct edge{
    int id,val,t;
};
struct node{
    int id,val;
    bool operator<(const node&x)const{
        return val>x.val;
    }
};
vector<edge>v[N];
int dis[N];
bool vis[N];
void Dijkstra(int st){
    priority_queue<node>q;
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    q.push({st,0});
    while(!q.empty()){
        int tx=q.top().id;
        q.pop();
        if(vis[tx])
            continue;
        vis[tx]=1;
        for(int i=0;i<v[tx].size();i++){
            int to=v[tx][i].id,tim=v[tx][i].t;
            int w=v[tx][i].val+((tim-dis[tx]%tim)%tim);//从u->v的总花费时间
            if(dis[to]>dis[tx]+w){
                dis[to]=dis[tx]+w;
                q.push({to,dis[to]});
            }
        }
    }
}
signed main(){
    cin>>n>>m>>X>>Y;
    for(int i=1;i<=m;i++){
        int x,y,t,k;
        cin>>x>>y>>t>>k;
        v[x].push_back({y,t,k});
        v[y].push_back({x,t,k});
    }
    Dijkstra(X);
    if(dis[Y]>1e18)//到不了
        cout<<-1;
    else
        cout<<dis[Y];
    return 0;
}