Atcoder beginer contest 252 (Dijkstra, reverse thinking)

E - Road Reduction

Carelessness ：
Given a simple undirected graph .
Find any spanning tree , Make from point 1 The sum of distances to all other points is the smallest

Ideas ：

In the spanning tree ,1 The distance to any point must be greater than or equal to that in the original figure 1 Distance to this point . therefore , If the two distances are equal , That is the optimal solution . let me put it another way , For each of these points , Find something that will enable him to 1 The edge with the smallest point distance should be reserved . If you think it over , You will find all the points on this path , They should also correspond to the shortest path in the original figure . So it's easy , Run it over dijkstra, For every point dis When the value is updated , Record the corresponding edge id, Finally, traverse the output . Because when each point is updated, the corresponding edge will not coincide with the edge corresponding to other points , that n-1 Just one point n-1 side , There is a spanning tree , So the strategy is reasonable .

code：
 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+10;
ll n,m;
struct ty{
	ll t,l,next,id;
}edge[N<<1];
ll cnt=0;
ll head[N];
void add(ll a,ll b,ll c,ll d){edge[++cnt].t=b;edge[cnt].l=c;edge[cnt].next=head[a];edge[cnt].id=d;head[a]=cnt;}
ll ans[N];
ll a,b,c;
ll vis[N],dis[N];
priority_queue<pair<ll,ll>> q;
void dij()
{
	dis[1]=0;
	memset(vis,0,sizeof vis);
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		ll ty=q.top().second;
		q.pop();
		if(vis[ty]++) continue;
		for(int i=head[ty];i!=-1;i=edge[i].next)
		{
			ll y=edge[i].t;
			if(vis[y]) continue;
			if(dis[y]<=dis[ty]+edge[i].l) continue;
			dis[y]=dis[ty]+edge[i].l;
			ans[y]=edge[i].id;
			q.push(make_pair(-dis[y],y));
		}
	}
}
int main()
{
	memset(head,-1,sizeof head);
	memset(dis,0x3f,sizeof dis);
	cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		cin>>a>>b>>c;
		add(a,b,c,i);
		add(b,a,c,i);
	}
	dij();
	for(int i=2;i<=n;++i) cout<<ans[i]<<' ';
	return 0;
}

F - Bread 

Carelessness ：
There is a long loaf of bread . You have a bunch of kids , Everyone has a required length of bread . One piece at a time with a length of k Cut the bread into two pieces , The cost is k（ The cost has nothing to do with the way of cutting ）, The minimum cost of meeting everyone's requirements .（ Long bread can be wasted ）

Carelessness ：
Personally, I think this question is better than E More water ...

Consider reverse thinking .

Combine two buns into one with a length of k The bread costs k The price of . And the combined total length of all the buns should be just the original length . Then use a priority queue , Just take two at a time . Because bread may be wasted , If the total length required is less than the original length , You have to add another difference to the queue （ If it's just right, you can't put 0 Put it in , Otherwise, it will contribute more ）.

Then the water fell ~（ Reverse thinking is very important ）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+10;
ll n,m;
ll mas[N];
ll sum=0;
priority_queue<ll, vector<ll>, greater<ll>> q;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		cin>>mas[i];
		sum+=mas[i];
		q.push(mas[i]);
	}
	if(m-sum>0) q.push(m-sum);
	ll ans=0;
	while(q.size()>=2)
	{
		ll a=q.top();
		q.pop();
		ll b=q.top();
		q.pop();
		ans+=a+b;
		q.push(a+b);
	}
	cout<<ans<<endl;
	return 0;
}