旅旅旅游

链接：https://ac.nowcoder.com/acm/contest/5158/E
来源：牛客网

题目描述
牛牛国有 nn 个城市，mm 条无向道路，每条道路三个属性 a_i,b_i,c_ia
i
​
,b
i
​
,c
i
​
，表示城市 a_ia
i
​
与城市 b_ib
i
​
之间有一条长为 c_ic
i
​
的道路，现在牛可乐在城市 11，他想去城市 nn。同时牛可乐非常聪明，他会将所有从1到 nn 可能的最短路径全都走一遍，之后便不再走了。

现在牛妹在城市 11，他想把所有城市走一遍，可是他不想走牛可乐走过的路，牛妹不知道他能不能将所有城市全走一遍，你能告诉她吗？

输入描述:
第一行两个数字 n,mn,m，表示城市的数量和道路的数量。

接下来 mm 行，每行 33 个数字 a_i,b_i,c_ia
i
​
,b
i
​
,c
i
​
，表示城市 a_ia
i
​
与城市 b_ib
i
​
之间有一条长为 c_ic
i
​
的道路 (题目保证无自环，可能有重边)

输出描述:
如果牛妹能走遍所有城市，输出 “YES” ，否则输出 “NO”。

示例1
输入
复制
4 5
1 2 2
1 3 2
2 3 1
2 4 2
3 4 1
输出
复制
YES
说明
城市1到城市4最短路距离是3(1->3->4)，牛妹不能走这些边也能走遍所有城市。

备注:
1\leq n\leq 1e5,1\leq m\leq 5e51≤n≤1e5,1≤m≤5e5
1\leq a_i,b_i\leq n,1\leq c_i\leq 1e91≤a
i
​
,b
i
​
≤n,1≤c
i
​
≤1e9
建议使用 scanf 读入

思路：判断一条边是否在最短路里面，需要从1号点走到n号点跑一次最短路，再从n号点到1号点跑一次最短路，然后枚举边，如果一条边的两个点正向和反向的和加上这个边等于最短路径长度的时候，那么就说明这个边在最短路径里边，跳过，如果不在的话，就把这两个点放入一个集合中，最后判断是否一个集合有n个点

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e6 + 10, M =3e6 + 10;
long long h[N], e[M], ne[M], w[M], idx;

typedef long long LL;
typedef pair<LL,LL> PII;

const LL INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
LL d[N], t[N];
LL p[N], cnt[N];
bool st[N];

void add(LL a, LL b, LL c){ 
   
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

struct Node{ 
   
	LL a, b, c;
}node[N];

LL find(LL x){ 
   
	if (x != p[x])   p[x] = find(p[x]);
	return p[x];
}

void dijkstra(LL u, LL dist[]){ 
   
	memset(dist, 0x7f, sizeof d);
// cout << dist[2] << endl;
	dist[u] = 0;
	memset(st, 0,sizeof st);
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({ 
   dist[u], u});
	//cout << dist[4] << "---------" << endl;
	
	while(heap.size()){ 
   
		auto t = heap.top();
		heap.pop();
		
		LL ver = t.second;
		LL distance = t.first;
		
	// cout << ver << "-------" << distance << endl;
		
		if (st[ver])   continue;
		st[ver] = true;
		
		for (LL i = h[ver]; ~i; i = ne[i]){ 
   
			LL j = e[i];
		// cout << j << "---------" << endl;
		// cout << dist[j] << endl;
			if (dist[j] > dist[ver] + w[i]){ 
   
				dist[j] = dist[ver] + w[i];
			// cout << "--------" << endl;
				heap.push({ 
   dist[j], j});
			}
		}
	}
}

int main(){ 
   
	scanf("%d%d", &n, &m);
	memset(h, -1, sizeof h);
	
	for (int i = 1; i <= m; i ++){ 
   
		LL a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);
		node[i] = { 
   a, b, c};
		add(a, b, c), add(b, a, c);
	}
	
	dijkstra(1, d);
	LL len = d[n];
    //cout << len << "-------" << endl;
	dijkstra((LL)n, t);
	//cout << t[1] << "======" << endl;
	
	for (LL i = 1; i <= n; i ++) { 
   
		p[i] = i;
		cnt[i] = 1;
	}
	
	for (int i = 1; i <= m; i ++){ 
   
		LL a = node[i].a;
		LL b = node[i].b;
		LL c = node[i].c;
		
	// cout << a << "-----" << b << "-------" << c <<endl;
	// cout << d[a] << " " << c << " " << t[b] << " " << d[b] << " " << c << " " << t[a] << endl; 
		if (d[a] + c + t[b] == len || d[b] + c + t[a] == len)     continue;
	// cout << "--------" << endl;
		LL pa = find(a), pb = find(b);
	// cout << "--------" << endl;
		if (pa != pb){ 
   
			p[pb] = pa;
			cnt[pa] += cnt[pb];
		}
	}
	
	bool flag = false;
	
	for (int i = 1; i <= n; i ++){ 
   
		if (cnt[i] == n)   flag = true;
	}
	
	if (flag)    cout << "YES" << endl;
	else   cout << "NO" << endl;
	
	return 0;
}

今天的文章旅旅旅游分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。