洛谷P3003 苹果交货Apple Delivery

题目描述

贝西有两个又香又脆的红苹果要送给她的两个朋友。当然她可以走的\(C（1 \leq C \leq 200000）\)条“牛路”都被包含在一种常用的图中，包含了\(P（1 \leq P \leq 100000）\)个牧场，分别被标为\(1..P\)。没有“牛路”会从一个牧场又走回它自己。“牛路”是双向的，每条牛路都会被标上一个距离。最重要的是，每个牧场都可以通向另一个牧场。每条牛路都连接着两个不同的牧场\(P1_i\)和\(P2_i（1<=P1_i,p2_i<=P)\)，距离为\(D_i\)。所有“牛路”的距离之和不大于\(2000000000\)。

现在，贝西要从牧场\(PB\)开始给\(PA_1\)和\(PA_2\)牧场各送一个苹果（\(PA_1\)和\(PA_2\)顺序可以调换），那么最短的距离是多少呢？当然，\(PB、PA_1\)和\(PA_2\)各不相同。

输入输出格式

输入格式：

Line \(1\): Line \(1\) contains five space-separated integers: \(C, P, PB, PA_1\), and \(PA_2\)
Lines \(2..C+1\): Line \(i+1\) describes cowpath i by naming two pastures it connects and the distance between them: \(P1_i, P2_i, D_i\)

输出格式：

Line 1: The shortest distance Bessie must travel to deliver both apples

输入输出样例

输入样例#1：

输出样例#1：

思路：一道裸的最短路题目，跟其他最短路题目不一样的是，这道题目要求的是起点到两个点的最短路之和，且这两个点可以调换，那么我们可以考虑以这两个点分别为起点，求到\(PB\)的最短路和到另一个点的最短路，然后取最小值。跑最短路用堆优化\(dijkstra\)即可。

代码：

#include<cstdio>

#include<algorithm>

#include<cctype>

#include<queue>

#include<cstring>

#define maxn 100007

using namespace std;

int n,m,num,head[maxn],s,a,b,dis[maxn];

inline int qread() {

  char c=getchar();int num=0,f=1;

  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

  for(;isdigit(c);c=getchar()) num=num*10+c-'0';

  return num*f;

}

struct Edge {

  int v,w,nxt;

}e[maxn<<2];

struct node {

  int x,y;

  bool operator < (const node &a) const{return y>a.y;}

};

inline void ct(int u, int v, int w) {

  e[++num].v=v;

  e[num].w=w;

  e[num].nxt=head[u];

  head[u]=num;

}

priority_queue<node>q;

inline void dijkstra(int s) {

  memset(dis,0x3f,sizeof(dis));

  q.push((node){s,0}),dis[s]=0;

  while(!q.empty()) {

    int u=q.top().x,d=q.top().y;

    q.pop();

    if(d!=dis[u]) continue;

    for(int i=head[u];i;i=e[i].nxt) {

      int v=e[i].v;

      if(dis[v]>dis[u]+e[i].w) {

        dis[v]=dis[u]+e[i].w;

        q.push((node){v,dis[v]});

      }

    }

  }

}

int main() {

  m=qread(),n=qread(),s=qread(),a=qread(),b=qread();

  for(int i=1,u,v,w;i<=m;++i) {

    u=qread(),v=qread(),w=qread();

    ct(u,v,w);ct(v,u,w);

  }

  dijkstra(a);

  int zrj=dis[s]+dis[b];

  dijkstra(b);

  int cyh=dis[s]+dis[a];

  printf("%d\n",min(cyh,zrj));

  return 0;

}

巴特西

洛谷P3003 苹果交货Apple Delivery

题目描述

输入输出格式

输入输出样例

最新文章

热门文章