最短路例题

baoyixu · 2021-12-09 18:48:01 · 个人记录

一、存储图

存储图，可以采用邻接矩阵和邻接表两种方式。对于无向图，可以把无向边看作两条方向相反的有向边，也就是都按有向图来存储处理，在后面讨论时以有向图为例，因此无向图边数量翻倍。

1. 邻接矩阵

2. 领接表

二、最短路重点算法

例题1：P3371 【模板】单源最短路径

【Dijkstra+堆优化】（弱化版）+（标准版）实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=5e5+10;
const long long INF=(1ll<<31)-1;   //注意由于位运算优先级低  注意要加括号 
int head[N],tot;
struct node{
    int to,dis,next;
}edge[M<<1];
int n,m;
long long d[N];
void add(int from,int to,int dis)
{
    edge[++tot].to=to;edge[tot].dis=dis;
    edge[tot].next=head[from];
    head[from]=tot;
}
bool vis[N];
void dijstra(int s)   //s是起点 
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        d[i]=INF;
    d[s]=0;
    priority_queue<pair<long long ,int> >que;
    que.push(make_pair(0,s));
    while(que.size())
    {
        int x=que.top().second;que.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,dis=edge[i].dis;
            if(d[y]>d[x]+dis)
            {
                d[y]=d[x]+dis;
                que.push(make_pair(-d[y],y));
            }           
        }
    }   
}
int main()
{
    int s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    dijstra(s);
    for(int i=1;i<=n;i++)
        printf("%lld ",d[i]);

    return 0;
}

利用spfa 更新所有状态空间：

#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=2e4+10;
struct node{
    int to,next,dis;
}edge[M];
int head[N],tot;
int n,p,k;
void add(int from,int to,int dis)
{
    edge[++tot].to=to,edge[tot].dis=dis;
    edge[tot].next=head[from];
    head[from]=tot;
}
int f[N][N],vis[N][N];
//f[i][k] 从起点走到i 经过k条免费线路的最低花费
void dp()
{
    memset(f,0x3f,sizeof(f));
    memset(vis,0,sizeof(vis));
    queue<pair<int,int> >que;
    que.push(make_pair(1,0));vis[1][0]=1;f[1][0]=0;
    while(que.size())
    {
        int x=que.front().first,xk=que.front().second;
        que.pop(); vis[x][xk]=0;
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,w=edge[i].dis;
            if(f[y][xk]>max(f[x][xk],w))
            {
                f[y][xk]=max(f[x][xk],w);
                if(vis[y][xk]==0)
                {
                    que.push(make_pair(y,xk));
                    vis[y][xk]=1;
                }               
            }
            if(xk+1<=k && f[y][xk+1]>f[x][xk])
            {
                f[y][xk+1]=f[x][xk];
                if(vis[y][xk+1]==0)
                {
                    que.push(make_pair(y,xk+1));
                    vis[y][xk+1]=1;
                }
            }           
        }       
    }
}
int main()
{
    cin>>n>>p>>k;
    for(int i=1;i<=p;i++)
    {
        int a,b,l;
        cin>>a>>b>>l;
        add(a,b,l);
        add(b,a,l);
    }
    dp();
    if(f[n][k]>=0x3f3f3f3f)cout<<-1;
    else cout<<f[n][k];

    return 0;
}

关于分层图最短路，经典的例子是[JLOI2011]飞行路线 但是，本题如果用普通队列版spfa进行，会超时，可以跑dijkstra最短路，即可以写成优先队列版本的spfa，参考代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=5e4+10;
struct node{
    int to,next,dis;
}edge[M<<1];
int head[N],tot;
int n,m,k;
void add(int from,int to,int dis)
{
    edge[++tot].to=to,edge[tot].dis=dis;
    edge[tot].next=head[from];
    head[from]=tot;
}
int f[N][11],vis[N][11];
//f[i][k] 从起点走到i 经过k条免费线路的最短距离 
int s,t;
void dp()
{
    memset(f,0x3f,sizeof(f));
    memset(vis,0,sizeof(vis));
    priority_queue<pair<int,pair<int,int> > >que;
    que.push(make_pair(0,make_pair(s,0)));vis[s][0]=1;f[s][0]=0;
    while(que.size())
    {
        int x=que.top().second.first,xk=que.top().second.second;
        que.pop(); vis[x][xk]=0;
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,w=edge[i].dis;
            if(f[y][xk]>f[x][xk]+w)
            {
                f[y][xk]=f[x][xk]+w;
                if(vis[y][xk]==0)
                {
                    que.push(make_pair(-f[y][xk],make_pair(y,xk)));
                    vis[y][xk]=1;
                }               
            }
            if(xk+1<=k && f[y][xk+1]>f[x][xk])
            {
                f[y][xk+1]=f[x][xk];
                if(vis[y][xk+1]==0)
                {
                    que.push(make_pair(-f[y][xk+1],make_pair(y,xk+1)));
                    vis[y][xk+1]=1;
                }
            }           
        }       
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d",&s,&t);
    s++,t++;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        a++,b++;
        add(a,b,c);
        add(b,a,c);
    }
    dp();
    int ans=1e9;
    for(int i=0;i<=k;i++)
        ans=min(ans,f[t][i]);

    cout<<ans;
    return 0;
}

P3008 [USACO11JAN]Roads and Planes G

本题带有负边权，不能直接dijkstra，直接spfa，会超时，USACO很爱卡spfa，优先队列版的spfa+O2也会超时1-2点，双端队列版的spfa可以卡过。 双端队列版的spfa参考代码如下：

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=25005,M=5e4;
struct node{
    int to,next,dis;
}edge[M<<2];
int head[N],tot;
int t,r,p,s;
void add(int from,int to,int dis)
{
    edge[++tot].to=to;  edge[tot].dis=dis;
    edge[tot].next=head[from];
    head[from]=tot;
}
int d[N],vis[N],cnt[N];
deque<int>que;
void spfa()
{
    for(int i=1;i<=t;i++)d[i]=INF;
    d[s]=0;vis[s]=1;
    que.push_back(s);   
    while(!que.empty())
    {   
        int x=que.front();  que.pop_front();
        vis[x]=0;
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,z=edge[i].dis;
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                if(vis[y])continue;
                vis[y]=1;
                if(que.size()>0 && d[y]<d[que.front()])
                    que.push_front(y);  
                else 
                    que.push_back(y);                       
            }
        }
    }
}
int main()
{
    scanf("%d%d%d%d",&t,&r,&p,&s);
    for(int i=1;i<=r;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);add(b,a,c);
    }
    for(int i=1;i<=p;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    spfa();
    for(int i=1;i<=t;i++)
        if(d[i]>=INF)
            printf("NO PATH\n");
        else printf("%d\n",d[i]);

    return 0;
}

本题正解，图有一个很强的性质：对于无向边，边权总是正的，因此每个无向边联通块是强联通的。而可能的负权边保证不能反向联通，因此把无向边联通块缩点后，得到的就是DAG。这样就可以在块内使用Dijkstra，块间利用拓扑排序更新答案。

判断负环问题

P2850 [USACO06DEC]Wormholes G

可以使用spfa判断负环，第一种方法，某个点进队次数超过n，那就肯定存在负环，这种方法相对而言慢一点。

第二种方法，设num[i]表示从起点s到i的最短路径包含的边数，num[s]=0,当d[y]>d[x]+w时，更新d[y]，同时更新num[y]=num[x]+1,如果发现num[y]>=n则图中存在负环，算法如果正常结束，就说明没有负环。 参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1e4;
struct node {
    int to,next ,dis;
} edge[M];
int head[N],tot,d[N],vis[N]; //d[i] 起点到i的最短距离
int num[N];  //num[i] 节点i被多少个节点更新
int n,m,w;
void add(int from,int to,int dis) {
    edge[++tot].to=to;
    edge[tot].dis=dis;
    edge[tot].next=head[from];
    head[from]=tot;
}
void spfa(int s) {
    memset(num,0,sizeof(num));
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[s]=0,vis[s]=1;
    num[s]=0;
    queue<int>que;
    que.push(s);
    while(que.size()) {
        int x=que.front();
        que.pop();
        vis[x]=0;
        for(int i=head[x]; i; i=edge[i].next) {
            int y=edge[i].to,w=edge[i].dis;
            if(d[y]>d[x]+w) {
                d[y]=d[x]+w;
                num[y]=num[x]+1;
                if(num[y]>n){
                    cout<<"YES\n";
                    return;
                }
                if(vis[y])continue;

                vis[y]=1;
                que.push(y);
            }
        }
    }
    cout<<"NO\n";
    return;
}
int main() {
    int t;
    cin>>t;
    while(t--) {
        tot=0;
        memset(head,0,sizeof(head));
        memset(edge,0,sizeof(edge));
        cin>>n>>m>>w;
        int u,v,p;
        for(int i=1;i<=m;i++)
        {
            cin>>u>>v>>p;
            add(u,v,p);
            add(v,u,p);
        }
        for(int i=1;i<=w;i++)
        {
            cin>>u>>v>>p;
            add(u,v,-p);
        }
        spfa(1);
    }
    return 0;
}

例题：求路径上边权乘积最小或最大 P2269 [HNOI2002]高质量的数据传输

题意：给定一张无向图，边权有两个，一个为丢失率pi（0<=p<=0.1），一个延时ti,求从起点到终点在丢失率最低的情况下，延时最低。

分析： 整个路径上丢失率的公式是 1-\prod_{i=1}^{n}(1-p_i) ，分析其含义，1-pi就是一条边不丢失率，相乘就是多条边的不丢失率，再与1做差，就是丢失率，那为了方便就直接计算不丢失率，就变成了从起点到终点的所有边权相乘，求不丢失率最高。

维护的是路径上边权乘积的最大值。 当然同时维护第二关键字，就是相等的情况下更新最小时间。

请问这种情况下dijkstra可以吗？

参考代码：点击

例题：P3943 星空

题意：给定n盏灯，其中k（k<=8）盏灯是灭的,给定m种操作长度，以操作长度为区间进行翻转，也就是原来是灭的变为亮的，原来是亮的转化灭的，最终使得n盏灯全亮，求最少操作步骤数。

抽象出来，就是给定一个0/1串，0代表灭，只能按照给定长度进行0/1翻转，求最少步骤数，使得串全部变为1。

【24分暴力】 对于前6个点可以直接状压求解，但是后面n太大就无能为力了。

【满分做法】 对于一段区间操作，经常转化为差分，但是本题差分怎么弄了？

由于是0和1的相互转化，我们差分就可以用异或取代做差。

若原数组为a[],差分数组为c[],定义c[i]=a[i]\wedge a[i-1],其中c[1]=a[1]。

根据异或的性质，c[1]\wedge c[2]\wedge c[3]\wedge ...c[n]=a[n]

若对原数组[L,R]这段进行翻转，就转成c数组c[L]=!c[L],c[R+1]=!c[R+1]

根据以上，举个例子：

原串为： 1011001

差分串： 11101011

若将区间[2,2]中的0变为1，就是差分数组中位置2和3进行取反，即两个1消掉；

若将区间[5,6]连续的0变为1，就是将差分数组中位置5和7进行取反。

如果原串中有k个0，差分串中1的个数肯定不超过2*k，也就是不超过16。

根据上面例子发现，对一段区间[L,R]取反一次（也就是操作一次），就是在差分数组位置L,R+1进行取反，那么最少的操作步骤应该就是消掉差分数组中成对的1，也就是两个1见面就抵消，位置i的1消掉位置j的1，这是有代价的，提前预处理这个代码。

提前预处理计算，将1移动距离为x的代价，可以使用spfa，由于操作一次代价是1，本质就是bfs最短路。

最后就是进行状态压缩：

其中d[pos[j]-pos[i]]就是消掉位置pos[i]和pos[j]上的1的代价。

参考代码：点击