标签：最短路

题目内容

P1119

大意：给定编号从 1 到 n-1 的村庄，每个村庄都被一定程度上损毁，而公路正常，在 t_i 时间前 i 号村庄不能通过，询问在 t 时间时 x 号和 y 号村庄能不能通车，如果能，最短路径是多少。

解题思路

这题思路真的很妙，让我们对 Floyd 的本质有了更深的理解，至少本蒟蒻是这样觉得的。

回归 Floyd 算法的本质：

for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])

实际上，Floyd 是通过枚举中转点 k 来求得每个点之间的最短路，本质上是一种 dp。

然后，注意到本题中，每个村庄的恢复时间是递增的，且给出的询问的时间也是递增的。而题目让我们求任意两点的最短路，那么也可以抽象成 Floyd。具体的方法就是，由于时间是递增的，所以每到一个村庄恢复的时间点我们就可以让这个村庄成为那个可以用来中转的 k 来更新这一时间的所有最短路。

在这题中，就是使用时间戳，保证回答被询问的时间前信息被更新过即可。注意村庄编号从 0 开始

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

const int maxn=205;
int n,m,t[maxn],f[maxn][maxn],q;

inline void floyd(int k)//更新信息的，通过给定可以中转的中转点来进行更新
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    return;
}

int main()
{
    n=read(),m=read();
    memset(f,0x3f,sizeof(f));//初始赋极大值 0x3f 不至于加起来爆int
    for(int i=0;i<n;i++)
        t[i]=read(),f[i][i]=0;
    while(m--)
    {
        int x=read(),y=read(),w=read();
        f[x][y]=f[y][x]=w;//双向边
    }
    q=read();
    int now=0;
    while(q--)
    {
        int x=read(),y=read(),s=read();
        while(t[now]<=s && now<n)//将这一时间前的所有时间信息更新
            floyd(now++);
        if(t[x]>s || t[y]>s || f[x][y]>=0x3f3f3f3f)//如果这一时间时村庄未修复，或者无路线
            printf("-1\n");//输出 -1
        else
            printf("%d\n",f[x][y]);//否则输出最短路即可
    }
    return 0;
}

题目内容

P4568

大意：n 个城市 m 条航线，可以免费掉最多 k 条航线，求从 s 到 t 的最少花费。

解题思路

分层图最短路模板，将图分成 k+1 层处理，每层之间照常连航线的边，跨层连免费航线，跑一遍最短路然后统计答案就可以了。每往下一层就相当于免费搭了一次飞机。

spfa 会被卡

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=1e4+5;

struct edge
{
    int to,dist;
    edge(){}
    edge(int b,int c)
    {
        to=b,dist=c;
    }
};

vector<edge> g[maxn*11];
int n,m,k,s,t;
queue<int> q;
bool vis[maxn*11];//记得空间开够
int d[maxn*11];

void ins(int u,int v,int w)
{
    g[u].push_back(edge(v,w));
    return;
}

void dij()//跑dij
{
    priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > q;
    memset(d,0x3f3f3f3f,sizeof(d));
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(auto &e:g[now])
            {
                if(d[e.to]>d[now]+e.dist)
                {
                    d[e.to]=d[now]+e.dist;
                    q.push(make_pair(d[e.to],e.to));
                }
            }
        }
    }
    return;
}

int main()
{
    scanf("%d %d %d",&n,&m,&k);
    scanf("%d %d",&s,&t);
    register int a,b,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        for(int j=0;j<=k;j++)//每层中间连
        {
            ins(a+n*j,b+n*j,c);
            ins(b+n*j,a+n*j,c);
            if(j<k)//跨层连
            {
                ins(a+n*j,b+(j+1)*n,0);
                ins(b+n*j,a+(j+1)*n,0);
            }
        }
    }
    dij();
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;i++)
        ans=min(ans,d[i*n+t]);
    printf("%d\n",ans);
    return 0;
}

题目内容

P1629

大意：有一邮递员送信，邮局为1节点，每次只能送1封，道路为单向，每条路需一定时间通过，求送完n-1封信要多长时间

解题思路

将这座城市抽象成一张图，可以发现每条路需通过的时间就是边的权值，求单源最短路即可。

但是：

注意到道路是单向的，所以邮递员不可能原路返回，这就是我犯的第一个错误（还好样例都没过，不然gg）

那怎么办，难道求1到所有点的最短路，再求所有点到1的最短路？显然不可能，复杂度爆炸，虽然Floyd优化之后可以勉强过，所以肯定有其他办法，就是

反向建图

将正常图的最短路算一遍，再将所有道路都反向了的反向图算一遍，两者加起来就是最终答案。

那反向图怎么建呢？

可以按照通常dij的思路，直接将所有数组复制一遍，然后写两个dij函数。但是这样不便于查错和维护，所以我选择OOP。考虑将一张图封装成一个类结构体，然后所有操作通过成员函数进行，这样的话方便维护而且代码量少一些。

具体实现细节见代码

#include <cstdio>
#include <queue>
#include <cstring>
#include <utility>
using namespace std;

const int maxn=1005;
int n,m;

struct edge//存储边的结构体
{
    int from,to,dist;
    edge(){}
    edge(int u,int v,int w)
    {
        from=u,to=v,dist=w;
    }
};

struct graph//这是定义的存储一张图的结构体
{
    vector<edge> g[maxn];//我使用vector存图
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > q;//dij时使用的优先队列
    int d[maxn];//存储从1到每个节点的距离
    bool vis[maxn];//存储是否被访问过
    void ins(int u,int v,int w)//加入边操作
    {
        g[u].push_back(edge(u,v,w));
        return;
    }
    void dijkstra()//dij本体
    {
        memset(d,0x3f3f3f3f,sizeof(d));
        memset(vis,false,sizeof(vis));
        d[1]=0;
        q.push(make_pair(0,1));
        while(!q.empty())
        {
            int now=q.top().second;
            q.pop();
            if(!vis[now])
            {
                vis[now]=true;
                for(auto &e:g[now])
                {
                    if(d[e.to]>d[now]+e.dist)
                    {
                        d[e.to]=d[now]+e.dist;
                        q.push(make_pair(d[e.to],e.to));
                    }
                }
            }
        }
    }
}a,b;//定义两个图分别存储正向和反向

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        a.ins(u,v,w);//记得正向存
        b.ins(v,u,w);//记得反向存
    }
    a.dijkstra(),b.dijkstra();//两边dij
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=a.d[i];
        ans+=b.d[i];
        //统计答案
    }
    printf("%d\n",ans);
    return 0;
}