Question

牛妹在城市 1，他想把所有城市走一遍，可是她不想走可以屬于從1到n的最短路的路徑，牛妹不知道他能不能將所有城市全走一遍，你能告訴她嗎？

Solution

djikstra 并查集

1. djikstra兩遍求從1到n的最短路和從n到1的最短路。
2. 判斷每一條路是否為最短路，若非最短路則將這兩點(diǎn)納入并查集同一個(gè)圈子之中。
   判斷條件：。
   之所以這么判斷和djisktra求兩次是為了避免是從還是的討論情況。

坑點(diǎn):INF一開(kāi)始開(kāi)的0x3f3f3f3f,然而實(shí)際上是不夠大，要是有過(guò)66.7%的應(yīng)該和我一樣。以后INF的大小還是自己結(jié)合數(shù)據(jù)判斷一遍吧

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;
}