牛客 NC24755 [USACO 2010 Dec S]Apple Delivery

题目描述

Bessie has two crisp red apples to deliver to two of her friends in the herd. Of course, she travels the C (1 <= C <= 200,000)
cowpaths which are arranged as the usual graph which connects P (1 <= P <= 100,000) pastures conveniently numbered from 1..P: no cowpath leads from a pasture to itself, cowpaths are bidirectional, each cowpath has an associated distance, and, best of all, it is always possible to get from any pasture to any other pasture. Each cowpath connects two differing pastures P1iP1_iP1i​ (1 <= P1iP1_iP1i​ <= P) and P2iP2_iP2i​ (1 <= P2iP2_iP2i​ <= P) with a distance between them of DiD_iDi​. The sum of all the distances DiD_iDi​ does not exceed 2,000,000,000.
What is the minimum total distance Bessie must travel to deliver both apples by starting at pasture PB (1 <= PB <= P) and visiting pastures PA1 (1 <= PA1 <= P) and PA2 (1 <= PA2 <= P)
in any order. All three of these pastures are distinct, of course.

Consider this map of bracketed pasture numbers and cowpaths with distances:
                3        2       2
           [1]-----[2]------[3]-----[4]
             \     / \              /
             7\   /4  \3           /2
               \ /     \          /
               [5]-----[6]------[7]
                    1       2
If Bessie starts at pasture [5] and delivers apples to pastures [1] and [4], her best path is:
      5 -> 6-> 7 -> 4* -> 3 -> 2 -> 1*
with a total distance of 12.

输入描述:

* Line 1: Line 1 contains five space-separated integers: C, P, PB, PA1, and PA2
* Lines 2..C+1: Line i+1 describes cowpath i by naming two pastures it connects and the distance between them: P1i,P2i,DiP1_i, P2_i, D_iP1i​,P2i​,Di​

输出描述:

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

示例1

输入

复制

9 7 5 1 4 
5 1 7 
6 7 2 
4 7 2 
5 6 1 
5 2 4 
4 3 2 
1 2 3 
3 2 2 
2 6 3 

输出

复制

12

思路：因为是双向边，因此p1到p2与p2到p1的距离是相等的，于是我们只需要比较p到p1和p到p2那个短再加上p1到p2就是答案；因为目的地数量较少所以可以直接通过两次求最短路找到答案，分别以p1和p2为起点

AC代码：

#include
#include
#include
#include
using namespace std;
 
#define PII pair
const int N=100010,M=400010;
 
int n,m,p1,p2,p;
int h[N],e[M],ne[M],w[M],idx;
int dist[3][N];
bool st[N];
queue<int>q ;
 
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
 
void dijkstra(int dist[],int s)
{
	memset(dist,0x3f,4*N);
	memset(st,0,sizeof st);
	dist[s]=0;
	
	priority_queue,greater> q;
	q.push({0,s});
	
	while(!q.empty())
	{
		PII t=q.top();
		q.pop();
		
		int ver=t.second,dis=t.first;
		
		if(st[ver])continue;
		st[ver]=true;
		
		for(int i=h[ver];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(dist[j]>dis+w[i])
			{
				dist[j]=dis+w[i];
				q.push({dist[j],j});
			}
		}
	}
}
 
int main()
{
	memset(h,-1,sizeof h);
	scanf("%d%d%d%d%d",&m,&n,&p,&p1,&p2);
	while(m--)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c),add(b,a,c);
	}
	dijkstra(dist[0],p1);
	dijkstra(dist[1],p2);
	
	cout<<min(dist[0][p],dist[1][p])+dist[0][p2];
}