题目见Luogu P5530
这是一道双权值SPFA树状数组优化最短路。
算法分析
首先，我们从题意中知道这个最短路是需要维护两个权值的。很显然，暴力枚举两种值是会TLE的，所以，我们需要做一些转化。当费用确定时，时间更短的路径是更优的。 于是，我们借用背包DP的思想，把费用看作需要消耗的容量，时间看做价值。 我们把各种状态加上一维，第一维表示结点编号，第二维表示费用，就是背包DP的状态，即\(dis_{i,j}\)，表示在\(i\)这个结点时，当费用为\(j\)时所需最小时间，则有：
\[ dis_{i,j}=min\{f_{k,i-cost_{k,i}}+time_{k,i} | edge_{k,i}\} \]
枚举每一条与\(i\)相连接的点\(k\)，从\(k\)结点转移到\(i\)结点，费用加了\(cost_{k,i}\)，时间加了\(time_{i,j}\)。再从最短路的角度看，我们还是跑SPFA，在队列中存两个值：下一个结点编号与费用。在对应的\(dis\)里更新。
最后，我们再统计一下答案，记一个\(now\) 初始\(now= \infty\)费用不断递增，如果\(dis_{t,i} < now\)，即又有一条可行的路径，答案加一，\(now = dis_{t,i}\)。
但是，。有没有什么技巧能够跑更快吗？
考虑这样的一个剪枝：对于状态\(dis_{i,j}\)，如果\(min\{dis_{i,0 \rightarrow j}\} > f_{i,j}\)，则进行更新。为什么这是正确的呢？看一看\(dis_{i,j}\)的定义：表示在\(i\)这个结点时，当费用为\(j\)时所需最小时间。如果费用增加了，时间却没有减少，走这条路显然没有之前的那条好。具体的，我们可以用树状数组维护区间\([0,j]\)的最小值。当然线段树也行，但是我们不需要那么多的功能，并且线段树常数时间较大，这道题不适用。
代码实现
#include <bits/stdc++.h>
using namespace std;
// IO优化
namespace IO
{
char buf[1<<15],*fs,*ft;
char out[1<<28],*fe=out;
inline char getc(){
return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++;
}
template <typename T>
inline void read(T &x){
x=0;
bool f=false;
char ch=getchar();
while (!isdigit(ch) && ch^'-') ch=getchar();
if (ch=='-') f=true, ch=getchar();
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
if(f)
x=-x;
return;
}
inline void flush(){
fwrite(out,1,fe-out,stdout);
fe=out;
}
template <typename T>
inline void writeln(T x){
if (!x) *fe++=48;
if (x<0) *fe++='-', x=-x;
T num=0, ch[20];
while (x) ch[++num]=x%10+48, x/=10;
while (num) *fe++=ch[num--];
*fe++='\n';
}
template <typename T>
inline void writesp(T x){
if (!x) *fe++=48;
if (x<0) *fe++='-', x=-x;
T num=0, ch[20];
while (x) ch[++num]=x%10+48, x/=10;
while (num) *fe++=ch[num--];
*fe++=' ';
}
}
int tot,n,m,s,t,ans;
// 树状数组类体
class BinaryIndexedTree
{
private:
int Arr[100005];
int lowbit(int x){
return x&-x;
}
public:
void modify(int pos,int val){ // 修改，维护最小值
pos++;
for(;pos<=n*100;pos+=lowbit(pos)){
Arr[pos]=min(Arr[pos],val);
}
}
int query(int pos){ // 查询最小值
++pos;
int ans=0x3f3f3f3f;
for(;pos;pos-=lowbit(pos)){
ans=min(ans,Arr[pos]);
}
return ans;
}
void clear(){ // 清空
memset(Arr,0x3f,sizeof(Arr));
}
};
struct Edge
{
int To,Next,Weight,Time; // 链式前向星
};
BinaryIndexedTree tree[105];
Edge e[605];
int head[105];
int dis[105][100005],vis[105][100005];
void link(int from,int to,int len,int tim){
e[++tot].To=to;
e[tot].Weight=len;
e[tot].Time=tim;
e[tot].Next=head[from];
head[from]=tot;
}
void spfa(int start){
queue<pair<int,int> > q;
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
for(int i=0;i<=n;i++) tree[i].clear();
q.push(make_pair(start,0));
tree[start].modify(0,0);
dis[start][0]=0;
vis[start][0]=1;
while(!q.empty()){
int u=q.front().first,w=q.front().second;
q.pop();
vis[u][w]=0;
for(int i=head[u];i;i=e[i].Next){
int v=e[i].To,neww=w+e[i].Weight; // w：费用，neww：新的费用
if(tree[v].query(neww)>dis[u][w]+e[i].Time){ // 剪枝
dis[v][neww]=dis[u][w]+e[i].Time; // 更新
tree[v].modify(neww,dis[v][neww]);
if(!vis[v][neww]){
vis[v][neww]=1;
q.push(make_pair(v,neww));
}
}
}
}
}
int main(){
IO::read(n); IO::read(m); IO::read(s); IO::read(t);
for(int i=1;i<=m;i++){
int x,y,l,t;
IO::read(x); IO::read(y); IO::read(l); IO::read(t);
link(x,y,l,t); link(y,x,l,t);
}
spfa(s);
int now=dis[0][0];
for(int i=0;i<=n*100;i++){
if(dis[t][i]<now){
ans++;
now=dis[t][i];
}
}
IO::writeln(ans);
IO::flush();
return 0;
}\(1000ms \rightarrow 100ms\)
所以下面还有一份速度更快但的代码，实测可以AC。QAQ~~
#include <bits/stdc++.h>
using namespace std;
namespace IO
{
char buf[1<<15],*fs,*ft;
char out[1<<28],*fe=out;
inline char getc(){
return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++;
}
template <typename T>
inline void read(T &x){
x=0;
bool f=false;
char ch=getchar();
while (!isdigit(ch) && ch^'-') ch=getchar();
if (ch=='-') f=true, ch=getchar();
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
if(f)
x=-x;
return;
}
inline void flush(){
fwrite(out,1,fe-out,stdout);
fe=out;
}
template <typename T>
inline void writeln(T x){
if (!x) *fe++=48;
if (x<0) *fe++='-', x=-x;
T num=0, ch[20];
while (x) ch[++num]=x%10+48, x/=10;
while (num) *fe++=ch[num--];
*fe++='\n';
}
template <typename T>
inline void writesp(T x){
if (!x) *fe++=48;
if (x<0) *fe++='-', x=-x;
T num=0, ch[20];
while (x) ch[++num]=x%10+48, x/=10;
while (num) *fe++=ch[num--];
*fe++=' ';
}
}
const int lim = 1e4 + 5;
int nxt[605], tim[605], cost[605], edge[605], head[605];
int q[1000005][2], dis[105][lim], vis[105][lim];
int minval[105][lim];
int tot, n, m, s, t, ans;
void link(int x, int y, int c, int t) {
nxt[++tot] = head[x];
head[x] = tot;
edge[tot] = y;
tim[tot] = t;
cost[tot] = c;
}
int query(int x, int y) {
++y;
int mn = 1e7;
for (; y; y -= (y & -y)) {
mn = min(mn, minval[x][y]);
}
return mn;
}
void modify(int x, int y, int val) {
++y;
for (; y <= n * 100; y += (y & -y)) {
minval[x][y] = min(minval[x][y], val);
}
}
void spfa() {
memset(dis, 63, sizeof(dis));
memset(minval, 63, sizeof(minval));
q[1][0] = s;
q[1][1] = 0;
dis[s][0] = 0;
vis[s][0] = 1;
modify(s, 0, 0);
for (int front = 1, back = 1; front <= back; ++front) {
int x = q[front][0], c = q[front][1];
vis[x][c] = 0;
for (int i = head[x], y; y = edge[i], i; i = nxt[i]) {
int newc = c + cost[i];
if (query(y, newc) > dis[x][c] + tim[i]) {
dis[y][newc] = dis[x][c] + tim[i];
modify(y, newc, dis[y][newc]);
if (!vis[y][newc]) {
vis[y][newc] = 1;
q[++back][0] = y;
q[back][1] = newc;
}
}
}
}
}
int main() {
IO::read(n); IO::read(m); IO::read(s); IO::read(t);
for (int i = 1; i <= m; ++i) {
int x, y, c, t;
IO::read(x); IO::read(y); IO::read(c); IO::read(t);
link(x, y, c, t);
link(y, x, c, t);
}
spfa();
int now = 0x3f3f3f3f;
for (int i = 0; i <= n * 100; ++i) {
if (dis[t][i] < now) {
++ans;
now = dis[t][i];
}
}
IO::writeln(ans);
IO::flush();
return 0;
}