C++11(clang++ 3.9) 解法, 执行用时: 640ms, 内存消耗: 41620K, 提交时间: 2020-04-19 13:39:42

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
long long d1[N],d2[N];
int fa[N],n,m;
struct node{
	int t;
	long long c;
	bool operator<(const node & rs)const{
		return c>rs.c;
	}
};
struct edge{
	int x,y,w;
}E[500005];
vector<node>vec[N];
int find(int u){
	if(u==fa[u])return u;
	return fa[u] = find(fa[u]);
}
void dij(int s,long long d[]){
	priority_queue<node>q;
	for(int i = 1;i<=n;i++)d[i] = 1e18;
	d[s] = 0;
	q.push({s,0});
	while(!q.empty()){
		node x = q.top();q.pop();
		if(d[x.t]<x.c)continue;
		for(int i = 0;i<vec[x.t].size();i++){
			node e = vec[x.t][i];
			if(d[e.t]>x.c+e.c){
				d[e.t]=x.c+e.c;
				q.push({e.t,d[e.t]});
			}
		}
	}
}
int main(){
	int a,b,c;
	scanf("%d%d",&n,&m);
	for(int i = 0;i<m;i++){
		scanf("%d%d%d",&a,&b,&c);
		vec[a].push_back({b,c});
		vec[b].push_back({a,c});
		E[i] = {a,b,c};
	}
	dij(1,d1);dij(n,d2);
	for(int i = 1;i<=n;i++)fa[i] = i;
	int cnt = n;
	for(int i = 0;i<m;i++){
		if(d1[E[i].x]+E[i].w+d2[E[i].y]==d1[n]||d2[E[i].x]+E[i].w+d1[E[i].y]==d1[n])continue;
		int u = find(E[i].x),v=find(E[i].y);
		if(u!=v){
			fa[u] = v;
			cnt--;
		}
	}
	if(cnt==1)printf("YES\n");
	else printf("NO\n");
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 1127ms, 内存消耗: 51984K, 提交时间: 2020-04-20 12:10:21

#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;
		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 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];
    set<int>sz;
	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;
		 sz.insert(e[i].u),sz.insert(e[i].v);
	}
	puts(sz.size()==n?"YES":"NO");
	return 0;
}