NC20568. [SCOI2012]滑雪与时间胶囊
描述
输入描述
输入的第一行是两个整数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; }