M_sea

洛谷1629 邮递员送信
题目描述有一个邮递员要送东西,邮局在节点1.他总共要送N-1样东西,其目的地分别是2~N。由于这个城市的交通比较繁...
扫描右侧二维码阅读全文
01
2017/10

洛谷1629 邮递员送信

题目描述

有一个邮递员要送东西,邮局在节点1.他总共要送N-1样东西,其目的地分别是2~N。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有M条道路,通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。

传送门

算法

这是一道图论题。

最小时间分为两个部分:第一部分是从1到其它点的最短路和,第二部分是从其它点到1的的最短路和。

所以这题的算法有这些:

Floyd

求出多源最短路径,直接加,期望得分30。

Dijkstra/SPFA

求出1的单源最短路径,然后将图反向,再求一遍1的单源最短路径。
为什么这样可以呢?首先第一次Dijkstra/SPFA是没问题的。至于第二部分,改完之后t到1的最短路自然变成了1到t的最短路,且权值并没有改变,所以也是正确的。

期望得分:100。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#define re register
using namespace std;
struct Edge //邻接表
{
    int to,dis;
    int nxt;
    Edge() { this->to=this->dis=this->nxt=0; }
}e[100010],fe[100010]; //有f的都是反图
int head[100010],fhead[100010];
int dis[1010],fdis[1010]; //单源最短路径
int edgenum=0,n,m;
inline void addEdge(int fr,int to,int d) //加边,同时添加正图和反图
{
    edgenum++;
    e[edgenum].to=to;
    e[edgenum].dis=d;
    e[edgenum].nxt=head[fr];
    head[fr]=edgenum;
    fe[edgenum].to=fr;
    fe[edgenum].dis=d;
    fe[edgenum].nxt=fhead[to];
    fhead[to]=edgenum;
}
struct HeapNode //Dijkstra堆节点
{
    int u,d;
    bool operator <(const HeapNode& rhs) const { 
//因为priority_queue本身是大根堆,所以<要反过来,
//这样就成了小根堆
        return d<rhs.d;
    }
};
inline void Dijkstra() //正图Dijkstra
{
    priority_queue<HeapNode> q; //堆
    for (re int i=1;i<=n;i++) dis[i]=2147483647; //初始化
    dis[1]=0; //1到1的最短路即为0
    q.push((HeapNode){1,0}); //节点1入堆
    while (!q.empty()) { //Dijkstra主过程
        HeapNode x=q.top(); q.pop(); //pop一个最小的
        int u=x.u;
        if (x.d!=dis[u]) continue; //已经被更新就返回
        for (re int i=head[u];i;i=e[i].nxt) { //更新相邻节点
            int v=e[i].to,w=e[i].dis;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w; //松弛
                q.push((HeapNode){v,dis[v]}); //入堆
            }
        }
    }
}
inline void fDijkstra() //反图Dijkstra,同上,不再注释orz
{
    priority_queue<HeapNode> q;
    for (re int i=1;i<=n;i++) fdis[i]=2147483647;
    fdis[1]=0;
    q.push((HeapNode){1,0});
    while (!q.empty()) {
        HeapNode x=q.top(); q.pop();
        int u=x.u;
        if (x.d!=fdis[u]) continue;
        for (re int i=fhead[u];i;i=fe[i].nxt) {
            int v=fe[i].to,w=fe[i].dis;
            if (fdis[u]+w<fdis[v]) {
                fdis[v]=fdis[u]+w;
                q.push((HeapNode){v,fdis[v]});
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int u,v,w;
    for (re int i=1;i<=m;i++) { //输入+建图
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
    }
    Dijkstra(); fDijkstra(); //跑正反Dijkstra
    int ans=0;
    for (re int i=2;i<=n;i++) ans+=(dis[i]+fdis[i]); //统计答案
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 18 PM

发表评论