链接：https://ac.nowcoder.com/acm/contest/26077/1036
来源：牛客网
题目描述
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
备注:
对于30% 的数据，1≤n≤20001 \le n \le 20001≤n≤2000；
对于100% 的数据，1≤n≤1051 \le n \le 10^51≤n≤105。
对于所有的数据，保证 1≤m≤1061 \le m \le 10^61≤m≤106 , 1≤hi≤1091 \le h_i \le 10^91≤hi≤109 ，1≤ki≤1091 \le k_i \le 10^91≤ki≤109。
分析
题目要求：到达的点数最多，并要求路径最短。
由于有时空胶囊的存在，从1号点能到达的点都是能到达的。
问题就变成了 从1号点 能到达的所有点所生成的最小生成树。
对于高度相同的点之间是无向边，高度高的点向高度低的点有有向边。
kruskal算法不能跑DAG的原因：无法确定每个被有向边连接到集合的点，都能通过其它有向边到达。
prim算法不能跑DAG的原因：无法确定当前选择的集合，通过有向边扩展到其它点的路径是最优的。
本题不能用kruskal算法的原因：如上，无法确定每个点都是如何被扩展的。可能有些点是无法到达的。
本题能用prim算法的原因：prim能到达的点都是确定能到达的，且本题同层的节点都是无向边，只有上层到下层是有向边，但是下层不能到达上册
可以下层到上层可以看成是距离无穷的有向边，这些边被选中也不会使路径更短，这样其实每条边都可以看成是无向边，也就从有向图转移成无向图了。
prim可以是部分有向图（有向图的相对边可以看成无穷大才行）
kruskal只能是无向图（就算看成无穷大，但是有些点它到不了也会连进去。）
至于起点，直接从1号点开始跑就可以了。
//-------------------------代码----------------------------
#define int ll
const int N = 1e5+10,M = 2e6+10;
int e[M],ne[M],w[M],h[N],idx;
int n,m;
void add(int a,int b,int c) {
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++ ;
}
int st;
struct node {
int id,h,dis;
bool operator<(const node&x) const {
if(h == x.h) return dis>x.dis;
return h < x.h;
}
};
node p[N];
int dist[N],ans = 0,cnt = 0;
bool vis[N];
void prim() {
st = 1;
priority_queue<node> q;
ms(dist,0x3f);
ms(vis,0);
dist[st] = 0;
q.push({st,p[st].h,p[st].dis});
while(q.size()) {
auto tmp = q.top();q.pop();
int ver = tmp.id;
if(vis[ver]) continue;
vis[ver] = 1;
cnt ++ ;ans += dist[ver];
int cnt = 0;
fe(i,ver) {
int j = e[i];
if(vis[j]) continue;
if(dist[j] > w[i]) {
dist[j] = w[i];
p[j].dis = w[i];
if(!vis[j]) q.push({j,p[j].h,dist[j]});
}
}
}
}
void solve()
{
cin>>n>>m;
int mx = 0;
ms(h,-1);
fo(i,1,n) {
cin>>p[i].h;
p[i].dis = inf;
if(p[i].h > mx) {
mx = max(mx,p[i].h);
st = i;
}
}
p[st].dis = 0;
fo(i,1,m) {
int u,v,w;
cin>>u>>v>>w;
if(p[u].h >= p[v].h)add(u,v,w);
if(p[v].h >= p[u].h)add(v,u,w);
}
prim();
cout<<cnt<<' '<<ans<<endl;
}
void main_init() {}
signed main(){
AC();clapping();TLE;
cout<<fixed<<setprecision(12);
main_init();
// while(cin>>n,n)
// while(cin>>n>>m,n,m)
// int t;cin>>t;while(t -- )
solve();
// {solve(); }
return 0;
}
/*样例区
*/
//------------------------------------------------------------
#include<bits/stdc++.h>#define TLE ios::sync_with_stdio(0),cin.tie(0)#define endl "\n"#define FILE "a"#define pb push_back#define gg exit(0);#define rt return;#define bd cout<<"debug"<<endl;#define db(x) cout<<#x<<':'<<x<<endl;#define dbb(i,a) cout<<#i<<':'<<i<<' '<<#a<<':'<<a<<' '<<endl;#define dbbb(i,a,b) cout<<#i<<':'<<i<<' '<<#a<<':'<<a<<' '<<#b<<':'<<b<<endl;#define TIME cout<<"RuningTime: "<<clock()<<"ms\n";#define YES cout<<"YES"<<endl;#define Yes cout<<"Yes"<<endl;#define NO cout<<"NO"<<endl;#define No cout<<"No"<<endl;#define None cout<<-1<<endl;#define el cout<<endl;#define x first#define y second#define V vector#define fo(i,j,n) for(int i = j;i<=n;i++)#define of(i,n,j) for(int i = n;i>=j;i--)#define fe(i,u) for(int i = h[u];~i;i=ne[i])#define all(a) a.begin(),a.end()#define alll(a) a.begin()+1,a.end()#define ms(a,b) memset(a, b, sizeof(a));#define tr_len(u) (tr[u].r - tr[u].l + 1)#define tr_mid (tr[u].l + tr[u].r >> 1)#define ul (u<<1)#define ur (u<<1|1)#define lowbit(x) (x&-x)#define gcd(a,b) __gcd(a,b)#define CLAP 11243using namespace std;void clapping() {#if CLAP == 1srand(time(NULL)+rand());freopen("a.in","r",stdin);freopen("a.out","w",stdout);//freopen("a.in","w",stdout);#endif}template<class T>inline void read(T &res) { char c;T flag = 1; while((c = getchar()) < '0' || c > '9') if(c == '-') flag = -1;res = c - '0'; while((c=getchar())>='0'&&c<='9')res=(res<<1)+(res<<3)+(c^48);res*=flag;}typedef pair<int,int> pii;typedef pair<long,long>pll;typedef long long ll;const int inf = 0x3f3f3f3f;const ll INF = 0x3f3f3f3f3f3f3f3fll;const double eps = 1e-8;int dy[] = {1,0,-1,0,1,1,-1,-1};int dx[] = {0,1,0,-1,1,-1,1,-1};template<class T> T qmi(T a,T b,T p) {T res = 1;for(;b;b>>=1,a=1ll*a*a%p)if(b&1)res = 1ll*res*a%p;return res;}template<class T> T exgcd(T a,T b,T &x,T &y) {if(b == 0) {x = 1;y = 0;return a;}ll d = gcd_ed(b,a%b,y,x);y = y - a / b * x;return d;}template<class T> T qmul(T a,T b,T p) {T res = 0;for(;b;b >>= 1,a = (a + a) % p) {res = (res + a) % p;}return res;}/*文档区
*/void AC(){ //// _oo0oo_// o8888888o// 88" . "88// (| -_- |)// 0\ = /0// ___/`---'\___// .' \\| |// '.// / \\||| : |||// \// / _||||| -:- |||||- \// | | \\\ - /// | |// | \_| ''\---/'' |_/ |// \ .-\__ '-' ___/-. /// ___'. .' /--.--\ `. .'___// ."" '< `.___\_<|>_/___.' >' "".// | | : `- \`.;`\ _ /`;.`/ - ` : | |// \ \ `_. \_ __\ /__ _/ .-` / /// =====`-.____`.___ \_____/___.-`___.-'=====// 佛祖保佑, 永无bug;}
//-------------------------代码----------------------------
#define int llconst int N = 1e5+10,M = 2e6+10;int e[M],ne[M],w[M],h[N],idx;int n,m;
void add(int a,int b,int c) { e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++ ;}int st;
struct node { int id,h,dis; bool operator<(const node&x) const { if(h == x.h) return dis>x.dis; return h < x.h; }};node p[N];int dist[N],ans = 0,cnt = 0;bool vis[N];void prim() { st = 1; priority_queue<node> q; ms(dist,0x3f); ms(vis,0); dist[st] = 0; q.push({st,p[st].h,p[st].dis}); while(q.size()) { auto tmp = q.top();q.pop(); int ver = tmp.id; if(vis[ver]) continue; vis[ver] = 1; cnt ++ ;ans += dist[ver]; int cnt = 0; fe(i,ver) { int j = e[i]; if(vis[j]) continue; if(dist[j] > w[i]) { dist[j] = w[i]; p[j].dis = w[i]; if(!vis[j]) q.push({j,p[j].h,dist[j]}); } } }}
void solve(){cin>>n>>m; int mx = 0; ms(h,-1); fo(i,1,n) { cin>>p[i].h; p[i].dis = inf; if(p[i].h > mx) { mx = max(mx,p[i].h); st = i; } } p[st].dis = 0; fo(i,1,m) { int u,v,w; cin>>u>>v>>w; if(p[u].h >= p[v].h)add(u,v,w); if(p[v].h >= p[u].h)add(v,u,w); } prim(); cout<<cnt<<' '<<ans<<endl;}void main_init() {}signed main(){AC();clapping();TLE;cout<<fixed<<setprecision(12);main_init();// while(cin>>n,n)// while(cin>>n>>m,n,m)//int t;cin>>t;while(t -- )solve();//{solve(); }return 0;}
/*样例区
*/
//------------------------------------------------------------
标签：DAG,prim,int,kruskal,st,景点,dist,define From： https://www.cnblogs.com/er007/p/16608612.html