CCYL Membership Activist

题解 P3003 【Apple Delivery】,USACO 2010 Dec - Silver

2021-08-03 11:00:02


不知道第多少篇最短路题解了……


现在看到这种题可以直接无脑 Dijkstra 了,毕竟在这种没有负环的题里 SPFA 没啥好处 ,掘墓鞭尸也不太道德啊


大部分同学对 Dijkstra 敬而远之的主要原因是运算符重载部分的问题,以下是运算符重载的代码:

bool operator < (const node &that) const {
    return dis>/*这里就是大于号*/that.dis;
}

补充一下为什么这里需要进行运算符重载,以及为什么重载运算符代码中的第 2 行使用了大于号:
此处的 Dijkstra 使用了优先队列,而优先队列默认从大到小排序(最大的元素最先出队)并使用小于号 < 进行比较,因此我们需要重载这个运算符(结构体没有自带的比较方式),并且为了实现 Dijkstra“数值较小的元素先出队”的操作,我们需要将这个运算符反过来。
事实上还有两种写法:

强迫症方法

首先正常重载一个大于号:

bool operator > (const node &that) const {
    return dis>that.dis;
}

然后开优先队列的时候这么写:

priority_queue<node,vector<node>,greater<node> >;

就行了,效果一样(使用了优先队列的另一种排序方式)。
我称其为强迫症方法,因为此处的大于号是真正意义上的“大于”。

pair 写法

STL 大法好。关于这种写法可以自己去查文档。


接下来是题目的主体:

  • 显然,题目中 Bessie 走过的路径可以概括为两段(PB 到 PA1/PA2 和 PA1/PA2 到 PA2/PA1)
  • 最优秀方案中 Bessie 需要走过的距离为
    $$\min [\textrm{dist(PB, PA1)},\textrm{dist(PB, PA2)}] + \textrm{dist(PA1, PA2)}$$$\color{silver}\tiny\text{*由于是无向图,PA1 和 PA2 的距离只需要求一次,不存在两个方向距离不同的问题}$
  • 其中 $\min$ 中的两项可以用任意单源最短路算法(不考虑复杂度情况下,本题中使用 Dijkstra)一次求出,PA1 和 PA2 的距离也可以如此得出

知道了这些,就可以直接上代码了:
$\color{silver}\tiny\text{*楼主还是推荐大家自己写写,毕竟这题实在是太水了……}$

//Luogu-P3003
//Luogu @Enterpr1se (Userid 363523)
//@_Qijia(Userid 363524) AK IOI!
#include<cstdio>
#include<cstring>
#include<queue>
#define regint register int
#define regshort register short
#define _Qijia using
#define AK namespace
#define IOI std
_Qijia AK IOI;
int p,c,pb,pa1,pa2,ecnt,last[100005],ans1,dist[100005],flag[100005],u,v,w;
int min(int a,int b){
    return a<b?a:b;
}
struct node{//Dijkstra 所使用的结构体 
    int id,dis;
    bool operator < (const node &that) const {
        return dis>that.dis;
    }
};
struct edge{//链式前向星
    int to,val,prev;
} fig[400005];
inline void add(int s,int e,int v){//链式前向星(加边) 
    ++ecnt;
    fig[ecnt]={e,v,last[s]};
    last[s]=ecnt;
    ++ecnt;
    fig[ecnt]={s,v,last[e]};
    last[e]=ecnt;
    return;
}
inline void Dijkstra(int stt/*起点*/){//Dijkstra 模板
    //开变量,初始化 
    node curr,targ;
    priority_queue<node> qu;
    memset(flag,false,sizeof(flag));
    memset(dist,0x3f,sizeof(dist));
    dist[stt]=0;
    qu.push({stt,0});

    while(qu.size()){
        curr=qu.top();
        qu.pop();
        flag[curr.id]=true;//注意 Dijkstra 是出队打标记(SPFA 是进队打) 
        for(regint i=last[curr.id];i;i=fig[i].prev){
            targ={fig[i].to,dist[curr.id]+fig[i].val};
            if(flag[targ.id]) continue;
            if(dist[targ.id]>targ.dis){
                dist[targ.id]=targ.dis;
                qu.push(targ);
            }
        }   
    }
    return;
}
int main(){
    scanf("%d%d%d%d%d",&c,&p,&pb,&pa1,&pa2);
    for(regint i=1;i<=c;++i)
        scanf("%d%d%d",&u,&v,&w),add(u,v,w);
    Dijkstra(pb);//以 PB 为起点做单源最短路 
    if(dist[pa1]<dist[pa2]){//若 PA1 更近,Ln64 
        ans1=dist[pa1];//保存 PB 到 PA1 的距离 
        Dijkstra(pa1);//以 PA1 为起点做单源最短路(求 PA1 和 PA2 之间的距离) 
        printf("%d",ans1+dist[pa2]);
    }
    else{//若 PA2 更近 
        ans1=dist[pa2];//保存 PB 到 PA2 的距离 
        Dijkstra(pa2);//以 PA2 为起点做单源最短路(求 PA2 和 PA1 之间的距离)
        printf("%d",ans1+dist[pa1]);
    }//Ln73
    return 0;
}

补充说明:
由于在求出 PB 到 PA1/PA2 中近者的距离后要求的只是 PA1 和 PA2 之间的距离(无向图,PA1 到 PA2 的距离和 PA2 到 PA1 的距离始终相等),本程序的 Ln64 到 Ln73 部分还有另一种写法:

ans1=min(dist[pa1],dist[pa2]);
Dijkstra(pa1);
printf("%d",ans1+dist[pa2]);

(这种做法明显更简洁,但是可能会逼死强迫症
$\mathtt{Thanks}\text{ }\mathtt{for}\text{ }\mathtt{reading.}\text{ }$