Question

牛妹在城市 1，他想把所有城市走一遍，可是她不想走可以属于从1到n的最短路的路径，牛妹不知道他能不能将所有城市全走一遍，你能告诉她吗？

Solution

djikstra 并查集

  1. djikstra两遍求从1到n的最短路和从n到1的最短路。
  2. 判断每一条路是否为最短路，若非最短路则将这两点纳入并查集同一个圈子之中。
    判断条件：。
    之所以这么判断和djisktra求两次是为了避免是从还是的讨论情况。

坑点:INF一开始开的0x3f3f3f3f,然而实际上是不够大，要是有过66.7%的应该和我一样。以后INF的大小还是自己结合数据判断一遍吧

Code

#include<bits/stdc++.h>
#define se second
#define fi first
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const ll LINF  = 0x3f3f3f3f3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e6 + 5;

int n,m;
ll u[N],v[N],w[N];

int f[N];

void init(int x) {for(int i=0;i<=x;i++) f[i]=i;}

int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}//路径压缩

void merge(int x, int y) {int a=find(x),b=find(y);if(a!=b) f[b]=a;}//“靠左”原则

struct edge{ll to,cost;};
vector<edge>G[N];
ll d[N],t[N];

void Dij(const int& s,const int& V,ll *d){
    priority_queue<P,vector<P>,greater<P> >q;
    fill(d,d+V+1,LINF);
    d[s]=0;
    q.push({0,s});
    while(!q.empty()){
        P t=q.top();q.pop();
        int v=t.se;
        if(d[v]<t.fi) continue;
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                q.push({d[e.to],e.to});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
        G[u[i]].push_back({v[i],w[i]});
        G[v[i]].push_back({u[i],w[i]});
    }
    Dij(1,n,d);
    Dij(n,n,t);
    ll len=d[n];
    init(n);
    for(int i=1;i<=m;i++){
        ll x=u[i],y=v[i],z=w[i];
        if(d[x]+z+t[y]==len||d[y]+z+t[x]==len) continue;
        int a=find(x),b=find(y);
        if(a!=b) merge(a,b);
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(f[i]==i) cnt++;
    }
    cout<<(cnt==1?"YES":"NO")<<'\n';
    return 0;
}