Skip to content

最短路

全源算法Floyd

Q.为什么中转点k要放在最外层？ A.因为floyd的实质是dp. 用f[k][i][j]表示经过i到j的通过1...k的路径

则 

f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j]);
由于最外面一层省略掉，所以得出floyd常见的式子； 但是：

“你要知道他是从上一层k转移过来的，所以当前的f[i][j]都应该是完成上一层动态规划的，如果k不是在最外层，那么f[i][j]就不是完成上一层动态规划的后的状态，有可能有的点没有经过k-1这个点的松弛。”

:)

全源之路径统计

P2047 (\(2^{11}-1\))

这道题，一开始思路是对的，后来越做越错orz

用C[i][j]表示i到j之间的最短路径数目

转移方程:(floyd==dp)

void floyd() {
    for(int k=1; k<=n; ++k) {
        for(int i=1; i<=n; ++i) {
            for(int j=1; j<=n; ++j) {
                if(i==j || i==k || j==k)continue;
                if(dis[i][j]>dis[i][k]+dis[k][j]) {
                    dis[i][j]=dis[i][k]+dis[k][j];
                    C[i][j]=C[i][k]*C[k][j];
                    continue;   
                }
                if(dis[i][j]==dis[i][k]+dis[k][j]){
                    C[i][j]+=C[i][k]*C[k][j];
                }
            }
        }
    }
    return;
}
统计答案:当dis[i][k]+dis[k][j]==dis[i][j]时，这条经过k的路径一定是i到j的最短路，则: 
void sum() {
    for(int k=1; k<=n; ++k) {
        for(int i=1; i<=n; ++i) {
            for(int j=1; j<=n; ++j) {
                if(i==k || j==k || i==j)continue;
                if(dis[i][k]+dis[k][j]==dis[i][j]) {
                    ans[k]+=(C[i][k]*C[k][j]*1.0)/(C[i][j]*1.0);
                }
            }
        }
    }
}
* 为什么floyd这种更新最短路条数的方式是对的呢，同一条路上的不同点会不会对这条路做出重复的贡献呢？
  • 其实是不会的，这是由于floyd是按中转点k的顺序实现的特性。

floyd

假设按照b,c,d的顺序(k)更新C[a][e]，则第一次C[a][e]=C[a][b]* C[b][e],因为C[b][e]没有更新过,其值为0，所以C[a][e]没有变化;c同b;只有d时，C[a][d]=C[d][e]=1,所以C[a][e]=1,符合实际情况。

换句话说，\(C[i][k]\)是现在，\(C[i][j]\)是未来，因为\(dp\)的无后效性，所以未来与过去无关，即与\(C[i][k]\)里面的小区间无关，不会被更新到。

综上，不会出现重复计算的情况，因为只有最后一次更新才有效。

分层图

  • 与网络流的建图类似，是一种特殊的建模

    P4568

这题有两种思路，一种是dp，另一种是分层图，我用的第一种

1.dp可以设dis[n][k]表示用k次免费优惠后到达n的最短路，则转移： 

        if(dis[v][k1]>dis[u][k1]+w && k1<=k){
                dis[v][k1]=dis[u][k1]+w;
                if(!vis[v][k1]){
                    q.push(node(dis[v][k1],v,k1));
                }
            }
            if(dis[v][k1+1]>dis[u][k1] && k1+1<=k){
                dis[v][k1+1]=dis[u][k1];
                if(!vis[v][k1+1]){
                    q.push(node(dis[v][k1+1],v,k1+1));
                }   
            }
        }
这里可以用结构体来保存每个节点用的k，在全都进队；

也可以直接在最外层枚举k，做k次最短路

2.分层图板子

直接建出k层0边，表示每个航班免费搭乘后用0费用跳转到目的地。

dijkstra

1.priority_queue写法，最常用，注意结构体构造函数和重载运算符的写法，别记错了。

struct node{
    int dis,pos;
   bool operator <(const node &x)const{
        return x.dis<dis; 
   }
   node(int d,int p){
    dis=d,pos=p;
   }
}e[N<<1];
void dijkstra()
{
    for(int i=0;i<N;++i)dis[i]=INF;
    dis[s] = 0;
    q.push( node(0,s) );
    while( !q.empty() )
    {
        node u = q.top().pos;
        q.pop();
        if( vis[u] )continue;
        vis[u] = 1;
        for( int i = head[u]; ~i; i = e[i].nxt )
        {
            int v = e[i].v,w=e[i].w;
            if( dis[v] > dis[u] + w )
            {
                dis[v] = dis[u] + w;
                if( !vis[v] )
                {
                    q.push( node (dis[v], v) );
                }
            }
        }
    }
}
2.手写堆：比第一种快了hin多，费用流等很多用到最短路且数据量很大的题就要用手写堆了，能快1倍左右。

P1629 模板题

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=1e4+10,M=2e5+10,INF=1e14;
struct hp{
    int dis,pos;
}heap[N];
struct node{
    int v,w,nxt,t;
}e[M<<1];
int head[N],dis[N],vis[N];
int cnt,n,m,u,v,w,tot;
void add(int u,int v,int w,int t){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].t=t;
    e[cnt].nxt=head[u];
    head[u]=cnt;
    return;
}
void push(int d,int p){
    heap[++tot].dis=d,heap[tot].pos=p;
    int now=tot;
    while(now>1){
        int nxt=now>>1;
        if(heap[nxt].dis<=heap[now].dis)break;
        swap(heap[nxt],heap[now]);
        now=nxt;
    }
    return;
}
int pop(){
    int ans=heap[1].pos;
    swap(heap[1],heap[tot]);
    tot--;
    int now=1;
    while(now*2<=tot){
        int nxt=now<<1;
        if(now*2+1<=tot && heap[nxt].dis>heap[nxt+1].dis)nxt++;
        if(heap[nxt].dis>=heap[now].dis)break;
        swap(heap[nxt],heap[now]);
        now=nxt;
    }
    return ans;
}
bool empty(){
    return tot==0;
}
void dij(){
    //memset(dis,0x3f,sizeof dis);
    for(int i=0;i<N;++i)dis[i]=INF;
    memset(vis,0,sizeof vis);
    dis[1]=0;
    tot=0;
    push(0,1);
    while(!empty()){
        int u=pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w,t=e[i].t;
            if(t && dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    push(dis[v],v);
                }
            }
        }
    }
    return;
}
signed main(){
    memset(head,-1,sizeof head);
    cnt=-1;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w,1);
        add(v,u,w,0);
    }
    dij();
    int ans=0;
    for(int i=2;i<=n;++i){
        ans+=dis[i];
    }
    for(int i=0;i<=m*2-1;i+=2){
        e[i].t=0;
        e[i^1].t=1;
    }
    dij();
    for(int i=2;i<=n;++i){
        ans+=dis[i];
    }
    printf("%lld",ans);
    return 0;
}

SPFA

~~据说它死了~~ bellman-ford 的民间加强版。 

bool SPFA(){
    int s=1;
    for(int i=0;i<N;++i)dis[i]=INF;
    memset(vis,0,sizeof vis);
    vis[s]=1;
    dis[s]=0;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}

二分节点

在一些题中会给你节点的权值，并要求经过的节点的权值最大值不超过k，求最短路。这时候，就可以二分权值的限制，将不满足的节点~~ban掉~~,然后跑最短路即可。

P1462 模板题

反向建边

经典的最短路解题方法

P1629 模板题

P5663

~~考场上送走我的题，祭我的2019~~

直接搜索直接爆炸，更何况我考场上根本没写对

我们发现，假设从\(u\)出发去\(v\),如果\(u,v\)之间的距离等于\(L\),那么所有距离\(u\)为\(L+2,L+4,...\)的点都可以到达；

而对于\(L+1\)，则不一定有，需要从\(L\)转移而来。

所以这道题变成了一道求奇偶路径的题。

奇偶路径就是指将整个图分成长度为奇数的路径核偶数的路径，并分别互相更新。

那么我们只需要\(dijkstra\)即可求出所有路径距离。

如果\(dis[a][t]>L(L \& 1= t)\),则不用提供零件,否则就要提供零件。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long 
using namespace std;
const int N=1e5+10;
int n,m,q,cnt,u,v,a,L;
int head[N],dis[N][2],vis[N][2];
struct edge{
    int v,nxt;
}e[N<<1];
struct node{
    int dis,pos,type;
    bool operator <(const node &x)const{
        return x.dis<dis;
    }
    node(int d,int p,int t){
        dis=d,pos=p,type=t;
    }
};
void add(int u,int v){
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}
void dij(int s){
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    priority_queue<node> q;
    q.push(node(0,s,0));
    dis[s][0]=0;

    while(!q.empty()){
        node tmp=q.top();q.pop();
        int u=tmp.pos,t=tmp.type;
        if(vis[u][t])continue;
        vis[u][t]=1;
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].v;
            if(dis[v][1]>dis[u][0]+1){
                dis[v][1]=dis[u][0]+1;
                if(!vis[v][1])q.push(node(dis[v][1],v,1));
            }
            if(dis[v][0]>dis[u][1]+1){
                dis[v][0]=dis[u][1]+1;
                if(!vis[v][0])q.push(node(dis[v][0],v,0));
            }
        }
    }
}
signed main(){
    memset(head,-1,sizeof head);
    cnt=-1;
    scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld",&u,&v);
        add(u,v),add(v,u);
    }   
    dij(1);
    for(int i=1;i<=q;++i){
        scanf("%lld%lld",&a,&L);
        if(L&1){
            if(dis[a][1]>L)printf("No\n");
            else printf("Yes\n");
        }else{
            if(dis[a][0]>L)printf("No\n");
            else printf("Yes\n");
        }
    }
    return 0;
}

P7997

~~又是考场上虐我千百遍的题~~

这题也是奇偶路径的板子题，如果一个数\(i\)小于\(a[j]\)，则一定可以去到\(i+a[j]\)后再回到\(i\);并且总点数只有\(2* MAXa=4000\)个点，所以直接最短路。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long 
using namespace std;
const int N=1e4+10,M=4e6+10;
int n,T,L,m,cnt,MAX;
int a[N],head[N],vis[N][2],dis[N][2],ans[N];
struct node{
    int dis,pos,type;
    bool operator <(const node &x)const{
        return x.dis<dis;
    }
    node(int d,int p,int t){
        dis=d,pos=p,type=t;
    }
};
struct edge{
    int v,nxt;
}e[M<<1];
void add(int u,int v){
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}
void init(){
    for(int i=0;i<=MAX+MAX-1;++i)
        for(int j=1;j<=n;++j)
            add(i,i>=a[j]?i-a[j]:i+a[j]);
}
void dij(int s){
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    priority_queue<node> q;
    q.push(node(0,s,0));
    dis[s][0]=0;
    while(!q.empty()){
        node tmp=q.top();q.pop();
        int u=tmp.pos,t=tmp.type;
        if(vis[u][t])continue;
        vis[u][t]=1;
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].v;
            if(dis[v][1]>dis[u][0]+1){
                dis[v][1]=dis[u][0]+1;
                if(!vis[v][1])q.push(node(dis[v][1],v,1));
            }
            if(dis[v][0]>dis[u][1]+1){
                dis[v][0]=dis[u][1]+1;
                if(!vis[v][0])q.push(node(dis[v][0],v,0));
            }
        }
    }
}
signed main(){
    memset(head,-1,sizeof head);
    cnt=-1;
    scanf("%lld%lld",&n,&T);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]),MAX=max(MAX,a[i]);
    init();
    dij(0);
    for(int i=1;i<=T;++i){
        scanf("%lld",&m);
        for(int i=MAX+MAX-1;i>=0;--i){
            if(dis[i][m&1]<=m){
                printf("%lld\n",i);
                break;
            }
        }
    }
    return 0;
}

P1027

~~sb题真麻烦，写nm两小时~~

就...直接最短路就行了，但建图贼麻烦。SPFA还没死。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
typedef double db;
const int N=1e3+10,INF=0x3f3f3f3f,M=1e6+10;
int cnt,n,m,T,s,A,B;
db tmp,t;
int num[N];
int vis[N],head[N];
db dis[N];
struct edge{
    int v,nxt;
    db w;
}e[M];
struct city{
    int x,y;
    db T;
}c[N];
inline db Dis(int i,int j){int _x=c[i].x-c[j].x,_y=c[i].y-c[j].y;return (db)sqrt(_x*_x+_y*_y);}
inline int _Dis(int i,int j){int _x=c[i].x-c[j].x,_y=c[i].y-c[j].y;return (_x*_x+_y*_y);}
inline int g(int x,int y){return 4*(x-1)+y;}
void add(int u,int v,db w){e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;}
void init(){for(int i=1;i<=4*s;++i)dis[i]=(db)INF;}
void cal(int i){
    int n1=g(i,1),n2=g(i,2),n3=g(i,3);
    int x1=c[n1].x, y1=c[n1].y, x2=c[n2].x, y2=c[n2].y, x3=c[n3].x, y3=c[n3].y;
    int ab=_Dis(n1,n2),bc=_Dis(n2,n3),ac=_Dis(n1,n3);
    int x4=0,y4=0;
    if(ab+ac==bc)x4=x2+x3-x1,y4=y2+y3-y1;
    if(ab+bc==ac)x4=x1+x3-x2,y4=y1+y3-y2;
    if(bc+ac==ab)x4=x1+x2-x3,y4=y1+y2-y3;
    c[g(i,4)].x=x4,c[g(i,4)].y=y4;
}

void SPFA(int S){
    queue<int> q;
    init();
    memset(vis,0,sizeof vis);
    dis[S]=0.0;vis[S]=1;
    q.push(S);
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].v;db w=e[i].w;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                if(!vis[v]) vis[v]=1,q.push(v); 
            }   
        }
    }
}
db Min(db a,db b){
    return a<b?a:b;
}
int main(){
    scanf("%d",&T);
    while(T--){
        memset(head,-1,sizeof head);
        cnt=-1;
        scanf("%d%lf%d%d",&s,&t,&A,&B);
        for(int i=1;i<=s;++i){
            for(int j=1;j<=3;++j) scanf("%d%d",&c[g(i,j)].x,&c[g(i,j)].y),num[g(i,j)]=i;
            cal(i);num[g(i,4)]=i;
            scanf("%lf",&tmp);
            for(int j=1;j<=4;++j) c[g(i,j)].T=tmp;
        }
        for(int i=1;i<=4*s;++i){
            for(int j=1;j<=4*s;++j){
                if(i==j)continue;
                if(num[i]==num[j]) add(i,j,c[i].T*Dis(i,j));
                else add(i,j,t*Dis(i,j));
            }
        }
        db ans=(db)INF;
        for(int i=0;i<=3;++i){
            SPFA(4*A-i);
            for(int j=0;j<=3;++j) ans=Min(ans,dis[4*B-j]);
        }
        printf("%.1lf\n",ans);
    }
    return 0;
}