[USACO 2010 Dec S]Apple Delivery

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.

C++14(g++5.4) 解法, 执行用时: 392ms, 内存消耗: 13148K, 提交时间: 2020-02-06 12:34:06

#include<bits/stdc++.h>
using namespace std;
int c,p,pb,pb1,pb2,d[250500];
struct node{
	int v,w;
	node(){
	}
	node(int a,int b){
		v = a ;
		w = b ;
	}
}; 
vector<node> E[250500];
priority_queue<pair<int,int> > q;
void dijkstra(int s){
	memset(d,0x3f,sizeof d);
	d[s] =0;	
	q.push(make_pair(0,s));
	while(!q.empty()){
		int x =q.top().second;
		q.pop();
		for(auto i: E[x]){
			int y =i.v,z=i.w;
			if(d[y] > d[x] +z){
				d[y] = d[x] + z;
				q.push(make_pair(-d[y],y));
			}
		} 
	}
}
int main(){
	cin >> c >> p >> pb >> pb1 >> pb2;
	while(c--){
		int u,v,w;
		cin>> u >> v >> w;
		E[u].push_back(node(v,w));
		E[v].push_back(node(u,w));
	}
	dijkstra(pb);
	int sum1 = d[pb1];
	int sum2 = d[pb2];
	dijkstra(pb1);
	sum1 += d[pb2];
	dijkstra(pb2);
	sum2 += d[pb1];
	cout<<min(sum1,sum2)<<endl;
	return 0;
}

C++ 解法, 执行用时: 183ms, 内存消耗: 11256K, 提交时间: 2022-02-22 11:39:53

#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
ll n,m,x1,x2,l1,l2,x3,idx,to[400001],nex[400001],head[100001],w[400001],d[100001];
priority_queue<pair<ll,ll>> q;
void add(ll x,ll y,ll c)
{
	to[++idx]=y,nex[idx]=head[x],head[x]=idx,w[idx]=c;
}
void dijs(ll st)
{
	for(ll a=1;a<=n;a++) d[a]=1e18;
	d[st]=0;
	q.push({0,st});
	while(!q.empty())
	{
		ll x=q.top().second;
		q.pop();
		
		for(ll i=head[x];i;i=nex[i])
		{
			ll y=to[i];
			if(d[y]>d[x]+w[i])
			{
				d[y]=d[x]+w[i];
				q.push({-d[y],y});
			}
		}
	}
}
int main()
{
	cin>>m>>n>>x1>>x2>>x3;
	for(ll a=1;a<=m;a++)
	{
		ll x,y,c;
		cin>>x>>y>>c;
		add(x,y,c);
		add(y,x,c);
	}
	dijs(x1);
	l1=min(d[x2],d[x3]);
	dijs(x2);
	l2=d[x3];
	cout<<l1+l2; 
}

详情