原文鏈接：https://www.cnblogs.com/ctjcalc/p/post3.html
題目見Luogu P5530
這是一道雙權值SPFA樹狀陣列優化最短路，
演算法分析
Copyright ? 2019 ctjcalc，轉載請注明URL，并給出原文鏈接，謝謝， 首先，我們從題意中知道這個最短路是需要維護兩個權值的，很顯然，暴力列舉兩種值是會`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}\)，
但是，這樣還是不能AC，有沒有什么技巧能夠跑更快嗎？
考慮這樣的一個剪枝：對于狀態\(dis_{i,j}\)，如果\(min\{dis_{i,0 \rightarrow j}\} > f_{i,j}\)，則進行更新，為什么這是正確的呢？看一看\(dis_{i,j}\)的定義：表示在\(i\)這個結點時，當費用為\(j\)時所需最小時間，如果費用增加了，時間卻沒有減少，走這條路顯然沒有之前的那條好，具體的，我們可以用樹狀陣列維護區間\([0,j]\)的最小值，當然線段樹也行，但是我們不需要那么多的功能，并且線段樹常數時間較大，這道題不適用，
代碼實作
Copyright ? 2019 ctjcalc，轉載請注明URL，并給出原文鏈接，謝謝， ```cpp #include超長代碼警告
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;
}
<div id="copyright">
Copyright ? 2019 ctjcalc，轉載請注明URL，并給出原文鏈接，謝謝，
</div>
~~然而，這份代碼是不能`AC`的，因為這道題經過一些變動后，時限~~$1000ms \rightarrow 100ms$~~，常數大的代碼過不去了，~~
所以下面還有一份速度更快但~~更丑~~的代碼，實測可以`AC`，QAQ\~\~
```cpp
#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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137156.html
標籤：其他