牛客小白月赛24 E旅旅旅游 ( 最短路 +并查集 +思维 )

题目链接

解题报告：
先求出1为起点的最短路dis1[],n为起点的最短路dis2[],然后枚举每条边<u,v>
若dis1[u]+w+dis2[v]==dis1[n] || dis2[u]+w+dis1[v]==dis1[n] 成立说明边<u,v> 存在最短路径中，反之亦然。
对于那么不在最短路径当中的边我们可以用并查集将他们维护在一个集合中，最后判断集合大小是否为 n。

#define first f
#define second s
#define ll long long
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define sl(p) strlen(p)
#define SZ(p) p.size()
#define pii pair<int,int>
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define fast_cin  ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
using namespace std;
const int MOD=1e9+7;
const int maxn=2e5+5;
const ll inf=2e18;

struct node
{
    int st,to,next,w;
}edge[maxn*10];
struct Node
{
    int to;
    ll val;
    bool operator <(const Node &ls)const {return ls.val<val;}
};
int head[maxn*10],cnt,f[maxn];
bool vis[maxn];
ll dis1[maxn],dis2[maxn];

void add(int from,int to,int w)
{
    edge[++cnt].next=head[from];
    edge[cnt].st=from;
    edge[cnt].to=to;
    edge[cnt].w=w;
    head[from]=cnt;
}
void dij_queue(int root,ll dis[])
{
    mem(vis,false);
    priority_queue<Node>q;
    vis[root]=true;
    dis[root]=0;
    q.push({root,0});
    Node pp,kk;
    while(!q.empty()){
        pp=q.top();q.pop();
        for(int i=head[pp.to];~i;i=edge[i].next){
            int to=edge[i].to,w=edge[i].w;
            if(!vis[to]&&pp.val+w<dis[to]){
                dis[to]=pp.val+w;
                vis[to]=true;
                q.push({to,dis[to]});
            }
        }
    }
}
int getfind(int x)
{
    return f[x]==x?x:f[x]=getfind(f[x]);
}
int main()
{
    mem(head,-1);
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    for(int i=1;i<=n;i++){
        dis1[i]=inf;dis2[i]=inf;f[i]=i;
    }
    dij_queue(1,dis1);
    dij_queue(n,dis2);
    for(int i=1;i<=cnt;i++){
        int from=edge[i].st,to=edge[i].to,w=edge[i].w;
        if(dis1[from]+w+dis2[to]!=dis1[n]&&dis2[from]+w+dis1[to]!=dis1[n]){
            int k1=getfind(from),k2=getfind(to);
            if(k1!=k2){f[k2]=k1;}
        }
    }
    int ans=1;
    for(int i=2;i<=n;i++){
        if(getfind(1)==getfind(i)){ans++;}
    }
    if(ans==n) printf("YES\n");
    else printf("NO\n");
    return 0;
}