#C240220E. 不递减路径

前言（Front talk)

$\qquad$一眼题，但是题解中处理的很精妙，所以记录一下：把点权当作当前的 $\verb!priority_queue!$ 比较的关键字就好了。

网址（Website）

$\qquad$ 题目详情 - 不递减路径 - Super

$\qquad$ 题解 - 不递减路径 - Super

题解（Solution）

$\qquad$这道题就是让求一条满足条件的路径，并且使经过的点的种类更多。

$\qquad$对于第一个条件 $A_U\le A_V$ ，我们可以在建边的时候就只连从$\ A_U\ $通往 $A_V$ 的边，如果两点的权值相等，就连一条双向边。

$\qquad$那么如何处理后面的点的种类的问题呢？在前面的想法的基础上，我们直接将边权赋给连边，最后要求的最大分数就自然转化成了一条最长路，只要权值不相等，边权就为 $1$ ，否则就是 $0$ ，直接跑一个 $Dijsktra$ 算法就好啦~q(≧▽≦q)

$\qquad$注意这里不能用 $vis$ 数组来记录当前的点有没有用过，因为我们的优先队列是优先找到当前的点权最小的点，而不是记录的 $dis$ 最大的点，直接用 $vst$ 数组会导致答案出问题（当然也可以给优先队列三个权值，一个记录点权，一个记录答案 $dis$ ，一个记录点的编号）。同时， $dis[1]=1$ 不要忘记，点 $1$ 自己也有编号。

代码（Code）

#include<bits/stdc++.h>
#include<queue>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;

vector<int> ft[N];
int n,m,a[N];

priority_queue<P> q;
int dis[N];

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("path");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	int Tim = clock();
	cin>>n>>m;For(i,1,n) a[i]=input(); 
	For(i,1,m){
		int x=input(),y=input();
		if(a[x]<=a[y]) ft[x].emplace_back(y);
		if(a[x]>=a[y]) ft[y].emplace_back(x);
	}
	
	q.emplace(-a[1],1),dis[1]=1;
	while(q.size()){
		int x=q.top().second;q.pop();
		for(auto y:ft[x]){
			int v=(int)(a[y]!=a[x]);
			if(dis[y]<dis[x]+v){
				dis[y]=dis[x]+v;
				q.emplace(-a[y],y);
			}
		}
	}
	
	cout<<(dis[n]==-inf?0:dis[n])<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1024.,0;
}