列表

详情


NC20568. [SCOI2012]滑雪与时间胶囊

描述

a180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和N个轨道之间的交点(同时也是景点),而且每个景点都有一编号i(1 ≤ i ≤ N)和一高度Hi。a180285 能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边,且i 的高度不小于j。 
与其他滑雪爱好者不同,a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点,他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。 
这是一种很神奇的药物,吃下之后可以立即回到上个经过的景点(不用移动也不被认为是 a180285 滑行的距离)。
请注意,这种神奇的药物是可以连续食用的,即能够回到较长时间 之前到过的景点(比如上上个经过的景点和上上上个经过的景点)。 
现在,a180285站在1号景点望着山下的目标,心潮澎湃。他十分想知道在不考虑时间 胶囊消耗的情况下,以最短滑行距离滑到尽量多的景点的方案(即满足经过景点数最大的前 提下使得滑行总距离最小)。你能帮他求出最短距离和景点数吗?

输入描述

输入的第一行是两个整数N,M。
接下来1行有N个整数Hi,分别表示每个景点的高度。
接下来M行,表示各个景点之间轨道分布的情况。每行3个整数,Ui,Vi,Ki。表示编号为Ui的景点和编号为Vi的景点之间有一条长度为Ki的轨道。

输出描述

输出一行,表示a180285最多能到达多少个景点,以及此时最短的滑行距离总和。

示例1

输入:

3 3 
3 2 1 
1 2 1 
2 3 1 
1 3 10

输出:

3 2

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 831ms, 内存消耗: 103196K, 提交时间: 2020-08-10 14:55:16

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,inf=1e18;
typedef long long ll;
struct edge{
	int y;
	ll z;
}; 
vector<edge>v[N];
struct node{
	int v,h;
	ll dist;
	bool operator<(const node &a)const{
	return h==a.h?dist>a.dist:h<a.h;
	}
};
int val[N],cnt,n,m,vis[N];
ll dist[N],ans;
void prim(){
	for(int i=1;i<=n;i++)dist[i]=inf;
	priority_queue<node>q;
	dist[1]=0;
	q.push({1,val[1],0});
	while(q.size()){
		node t=q.top();q.pop();
		int x=t.v;
		if(vis[x])continue;
		vis[x]=1;
		cnt++;ans+=dist[x];
		for(int i=0;i<v[x].size();i++){
			int y=v[x][i].y;
			ll z=v[x][i].z;
			if(!vis[y]&&dist[y]>z){
				dist[y]=z;
				q.push({y,val[y],dist[y]});
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&val[i]);
	for(int i=1,x,y;i<=m;i++){
		ll z;
		scanf("%d%d%lld",&x,&y,&z);
		if(val[x]>=val[y])v[x].push_back({y,z});
		if(val[y]>=val[x])v[y].push_back({x,z});
	}
	prim();
	cout<<cnt<<" "<<ans<<endl;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1437ms, 内存消耗: 42920K, 提交时间: 2022-08-24 09:57:13

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n,m,h[100001],vis[100001],cnt;
long long ans;
vector<pair<int,int>>map[100001];
struct node
{
	int d,h,id;
	friend bool operator<(node a,node b)
	{
		return a.h==b.h?a.d>b.d:a.h<b.h;
	}
};
priority_queue<node>q;
void solve()
{
	q.push({0,h[1],1});
	while(!q.empty())
	{
		node now=q.top();
		q.pop();
		if(vis[now.id])continue;
		vis[now.id]=1;
		cnt++;
		ans+=now.d;
		for(int i=0;i<map[now.id].size();i++)
		{
			int ne=map[now.id][i].first;
			if(!vis[ne])q.push({map[now.id][i].second,h[ne],ne});
		}
	}
	cout<<cnt<<" "<<ans<<"\n";
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>h[i];
	for(int i=1;i<=m;i++)
	{
		int l,r,d;
		cin>>l>>r>>d;
		if(h[l]>=h[r])map[l].push_back({r,d});
		if(h[r]>=h[l])map[r].push_back({l,d});
	}
	solve();
	return 0;
}

上一题