题目内容

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;
}
最后修改日期:2020年2月3日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。