考虑分层图。
把图按速度分成 \(V\) 层，\(f_{i,j}\) 表示点 \(i\) 在第 \(j\) 层（速度为 \(j\)）的编号。注意：这里的速度为 \(j\) 是指到达 \(i\) 那一条边的速度（\(i\) 为终点）。
考虑一种 naive 的建边方式：
首先，记当前点为 \(u\)，速度为 \(i\)；\(u\) 的出边速度为 \(j\)，长度为 \(l\)，终点为 \(v\)。
-
\(j\not=0\)：遍历 \(u\) 的每条入边、出边，从 \(f_{u,i}\to f_{v,j}\) 连一条边权为 \(\frac{l}{j}\) 的边。
-
\(j=0\)：对于每一层 \(k\)，都从 \(f_{u,k}\to f_{v,k}\) 连一条长度为 \(\frac{l}{k}\) 的边。
\(j=0\) 时没什么优化空间，但是 \(j\not=0\) 时，建出来边的数量是 \(\text{indeg}(u)\times \text{oudeg}(u)\) 级别的，非常的寄。
那么，有没有什么优化方法呢？
注意到，对于 \(j\not=0\)，每个 \(f_{u,i}\) 向 \(f_{v,j}\) 连的边权是一样的。因此我们考虑对每个点建立一个“超级点”用于中转，记为 \(super_i\)。然后，对于每个 \(f_{i,j}\)，都向 \(super_i\) 连一条权值为 \(0\) 的边。这样，对于 \(j\not=0\) 时，直接从 \(super_u\to f_{v,j}\) 连权值为 \(\frac{l}{j}\) 的边即可。
注意到一开始的速度为 \(70\)，所以从 \(f_{0,70}\) 出发跑最短路。由于每个 \(f_{i,j}\) 都向 \(super_i\) 连边，所以 \(dis_{super_i}=\min_{j=1}^{V}dis_{f_{i,j}}\)。那么直接输出 \(dis_{super_d}\) 即可。
最后注意要输出路径，所以要记录每个点实际上应该是那个点，然后去重。
时间复杂度 \(O(V(n+m)\log V(n+m))\)。
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define gt getchar
#define pt putchar
typedef long long ll;
const int N=155;
const int M=1e7+5;
const int V=505;
using namespace std;
using namespace __gnu_pbds;
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
x=0;bool sgn=0;char ch=gt();
while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
if(sgn) x=-x;
}
template<class T,class ...T1> inline void read(T &x, T1 &...x1){
read(x);
read(x1...);
}
template<class T> inline void print(T x){
static char st[70];short top=0;
if(x<0) pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top) pt(st[top--]);
}
template<class T> inline void printsp(T x){
print(x);
putchar(' ');
}
template<class T> inline void println(T x){
print(x);
putchar('\n');
}
inline void put_str(string s){
int siz=s.size();
for(int i=0;i<siz;++i) pt(s[i]);
printf("\n");
}
struct edge{
int to,nxt;
double w;
}e[M];
int head[M],cnt,n,m,d,f[N][V],tot,super[N],pre[M],id[M];
// f[i][j]:点 i 在层 j（速度为 j）的编号
// super[i]:点 i 的超级源点
// id[i]:建出来的点 i 实际上是哪个点
inline void add_edge(int f,int t,double w){
e[++cnt].to=t;
e[cnt].w=w;
e[cnt].nxt=head[f];
head[f]=cnt;
}
struct Pair{
double val;
int pos;
Pair(double _val=0,int _pos=0):val(_val),pos(_pos){}
inline bool operator>(const Pair &b)const{return val>b.val;}
};
double dis[M];
bool vis[M];
priority_queue<Pair,vector<Pair>,greater<Pair> >pq;
inline void dijkstra(int s){
for(int i=1;i<=tot;++i) dis[i]=1e9;
dis[s]=0;
pq.push(Pair(0,s));
while(pq.size()){
int u=pq.top().pos;
pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
pre[v]=u;
pq.push(Pair(dis[v],v));
}
}
}
}
int stk[M],top;
inline void print_path(int t){
while(pre[t]){
stk[++top]=t;
t=pre[t];
}
stk[top+1]=-1;
printsp(0);
for(int i=top;i;--i) if(id[stk[i]]!=id[stk[i+1]]) printsp(id[stk[i]]);
}
signed main(){
read(n,m,d);
for(int i=0;i<n;++i){
for(int j=1;j<=500;++j){
f[i][j]=++tot;
id[tot]=i;
}
}
for(int i=0;i<n;++i) super[i]=++tot,id[tot]=i;
for(int i=0;i<n;++i){
for(int j=1;j<=500;++j){
add_edge(f[i][j],super[i],0);
}
}
for(int i=1;i<=m;++i){
int u,v,speed,len;
read(u,v,speed,len);
if(speed){
add_edge(super[u],f[v][speed],1.0*len/speed);
}else{
for(int j=1;j<=500;++j){
add_edge(f[u][j],f[v][j],1.0*len/j);
}
}
}
dijkstra(f[0][70]);
print_path(super[d]);
return 0;
}
然而，真的要把 \(500\) 层建出来吗？
我们照常建图。设 \(dis_{i,j}\) 表示到点 \(i\) 时速度为 \(j\) 时的最短路。然后分讨（延用上文的记号）：
-
\(j\not=0\)：用 \(dis_{u,i}+\frac{l}{j}\) 更新 \(dis_{v,j}\)。
-
\(j=0\)：用 \(dis_{u,i}+\frac{l}{i}\) 更新 \(dis_{v,i}\)。
然后就做完了？
然而，该做法和原本的 naive 做法是等效的，转移数还是 \(\deg\times \deg\) 的。
考虑改进算法：设 \(g_i\) 表示 \(\min_{j=1}^{V}dis_{i,j}\)，起到和原来的 \(super_i\) 一样的效果。然后建两个图，一个存 \(0\) 边，一个存非 \(0\) 边。然后修改 Dijkstra 的过程：
首先修改优先队列，把里面的元素修改为 \((\text{点},\text{dis 值},\text{速度})\)，然后按 \(dis\) 排序。
一开始，我们往堆中加入两个元素：\((0,0,70)\) 和 \((0,0,-1)\)，为什么会有 \(-1\) 后面会讲。
现在假设取出了堆顶元素 \((u,dis_{u,i},i)\)，然后按以下流程执行代码：
\(1.\) 如果 \(i\not=-1\) 且 \(dis_{u,i}<g_u\)，更新 \(g_u=dis_{u,i}\)，并记录 \(g_u\) 是由速度 \(i\) 得来的（因为要输出路径）。然后往堆里加入一个 \((u,g_u,-1)\)，跳至 \(2\)。
\(2.\) 如果 \(i\not=-1\)，遍历所有 \(0\) 边，用 \(dis_{u,i}+\frac{l}{i}\) 更新 \(dis_{v,i}\)，然后满足条件入堆，并记录前驱。
\(3.\) 如果 \(i=-1\)，此时的 \(dis\) 显然就是 \(g\)。只有在这种时候才去更新非 \(0\) 边，用 \(dis_{u,i}+\frac{l}{j}\) 更新 \(dis_{v,j}\)，然后入堆并记录前驱。
显然，一开始 \(g_0\) 就确定了，明显 \(=0\)。所以我们需要加入点 \((0,0,-1)\)。
最后答案就是 \(g_d\)。
时间复杂度大约是 \(O((n+m)\log m)\)。DarkBZOJ 上快了 \(400ms\) 左右，Luogu 快了 \(250ms\)左右。
输出路径用 Dijkstra 时记录的前驱即可，具体见代码：
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define gt getchar
#define pt putchar
typedef long long ll;
const int N=155;
const int M=1e7+5;
const int V=505;
using namespace std;
using namespace __gnu_pbds;
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
x=0;bool sgn=0;char ch=gt();
while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
if(sgn) x=-x;
}
template<class T,class ...T1> inline void read(T &x, T1 &...x1){
read(x);
read(x1...);
}
template<class T> inline void print(T x){
static char st[70];short top=0;
if(x<0) pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top) pt(st[top--]);
}
template<class T> inline void printsp(T x){
print(x);
putchar(' ');
}
template<class T> inline void println(T x){
print(x);
putchar('\n');
}
inline void put_str(string s){
int siz=s.size();
for(int i=0;i<siz;++i) pt(s[i]);
printf("\n");
}
struct Graph{
int head[N],cnt;
struct edge{
int to,nxt;
int w,speed;
}e[M];
inline void add_edge(int f,int t,int w,int speed){
e[++cnt].to=t;
e[cnt].w=w;
e[cnt].speed=speed;
e[cnt].nxt=head[f];
head[f]=cnt;
}
}G1,G2;
// G1:speed not = 0
// G2:speed = 0
int n,m,d;
struct Pair{
int pos,speed;
double val;
Pair(int _pos=0,double _val=0.0,int _speed=0):pos(_pos),val(_val),speed(_speed){}
inline bool operator>(const Pair &b)const{return val>b.val;}
};
int pos[N];
pair<int,int>pre[N][V];
double dis[N][V],g[N];
bool vis[N][V];
priority_queue<Pair,vector<Pair>,greater<Pair> >pq;
inline void dijkstra(int s){
for(int i=0;i<n;++i){
g[i]=1e9;
for(int j=1;j<=500;++j) dis[i][j]=1e9;
}
dis[s][70]=0,g[s]=0,pos[s]=70;
pq.push(Pair(s,0,70));
pq.push(Pair(s,0,-1));
while(pq.size()){
int u=pq.top().pos,speed=pq.top().speed;
pq.pop();
if(speed==-1){
for(int i=G1.head[u];i;i=G1.e[i].nxt){
int v=G1.e[i].to,sp=G1.e[i].speed;
double w=1.0*G1.e[i].w/sp;
if(dis[v][sp]>g[u]+w){
dis[v][sp]=g[u]+w;
pre[v][sp]=make_pair(u,speed);
pq.push(Pair(v,dis[v][sp],sp));
}
}
}else{
if(vis[u][speed]) continue;
vis[u][speed]=1;
if(dis[u][speed]<g[u]){
g[u]=dis[u][speed];
pos[u]=speed;
pq.push(Pair(u,g[u],-1));
}
for(int i=G2.head[u];i;i=G2.e[i].nxt){
int v=G2.e[i].to;
double w=1.0*G2.e[i].w/speed;
if(dis[v][speed]>dis[u][speed]+w){
dis[v][speed]=dis[u][speed]+w;
pre[v][speed]=make_pair(u,speed);
pq.push(Pair(v,dis[v][speed],speed));
}
}
}
}
}
int stk[N],top;
inline void print_path(int t){
int speed=pos[t];
while(t){
stk[++top]=t;
int fst=pre[t][speed].first;
int scd=pre[t][speed].second;
if(scd==-1) scd=pos[fst];
t=fst,speed=scd;
}
printsp(0);
for(int i=top;i;--i) printsp(stk[i]);
}
signed main(){
read(n,m,d);
for(int i=1;i<=m;++i){
int u,v,speed,len;
read(u,v,speed,len);
if(speed) G1.add_edge(u,v,len,speed);
else G2.add_edge(u,v,len,0);
}
dijkstra(0);
print_path(d);
return 0;
}