牛客小白月赛24 E.旅旅旅游(最短路&并查集）

牛客小白月赛24 E.旅旅旅游(最短路&并查集）

题目传送门

思路：

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=5e5+5;
typedef long long ll;
ll d1[N],d2[N];
int n,m,s[N];
struct node{
    ll d;
    int id;
    bool operator<(const node &a)const{
        return d>a.d;
    }
}now; 
vector<node>vi[N];
struct edge{
    int u,v,w;
}e[M];
void dij(int x,ll dis[]){
    for(int i=1;i<=n;i++) dis[i]=1e15;
    dis[x]=0;
    priority_queue<node>q;
    q.push({dis[x],x});
    while(q.size()){
        now=q.top();q.pop();
        if(dis[now.id]<now.d) continue;//代替了vis[i]的作用. 
        int u=now.id;
        for(auto it:vi[u]){
            int v=it.id,w=it.d;
            if(dis[v]>dis[u]+w)
                dis[v]=dis[u]+w,q.push({dis[v],v});
        }
    }
}
int find(int x){
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v,w;i<=m;i++){
         scanf("%d%d%d",&u,&v,&w);
         vi[u].push_back({w,v});
         vi[v].push_back({w,u});
         e[i]={u,v,w}; 
    }
    dij(1,d1);
    dij(n,d2);
    ll mn=d1[n];
    int cnt=n;
    for(int i=1;i<=n;i++) s[i]=i;
    for(int i=1;i<=m;i++){
         if(d1[e[i].u]+d2[e[i].v]+e[i].w==mn||d1[e[i].v]+d2[e[i].u]+e[i].w==mn) continue;
         int fa=find(e[i].u),fb=find(e[i].v);
         if(fa!=fb){
            s[fa]=fb;
            cnt--;
         }
    }
    puts(cnt==1?"YES":"NO");
    return 0;
}