Luogu

算法

显然,最短距离只有两种可能:

  • $P_B$->$P_{A_1}$->$P_{A_2}$
  • $P_B$->$P_{A_2}$->$P_{A_1}$

那么以$P_{A_1}$和$P_{A_2}$为源点,跑最短路,比较即可。

注意输入是无向边。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Edge { int v,w,nxt; };
Edge e[400010];
int head[100010],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v; e[cnt].w=w;
    e[cnt].nxt=head[u]; head[u]=cnt;
}

struct Heapnode {
    int u,d;
    bool operator <(const Heapnode& rhs) const {
        return d>rhs.d;
    }
};

int dis[100010];

inline void Dijkstra(int s) {
    priority_queue<Heapnode> Q;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0; Q.push((Heapnode){s,0});
    while (!Q.empty()) {
        Heapnode fr=Q.top(); Q.pop();
        int u=fr.u,d=fr.d;
        if (d!=dis[u]) continue;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w;
                Q.push((Heapnode){v,dis[v]});
            }
        }
    }
}

int main() {
    int n,m,s,t1,t2;
    m=read(),n=read(),s=read(),t1=read(),t2=read();
    for (re int i=1;i<=m;i++) {
        int a=read(),b=read(),c=read();
        addEdge(a,b,c);
        addEdge(b,a,c);
    }
    Dijkstra(t1); int ans1=dis[s]+dis[t2];
    Dijkstra(t2); int ans2=dis[s]+dis[t1];
    printf("%d\n",min(ans1,ans2));
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 02 PM