Dij求调
查看原帖
Dij求调
448018
KAqwq楼主2023/8/16 20:04

我的样例输出为

4294967294
2147483647
4294967294

求救

#include <bits/stdc++.h>
#define IOS std::ios::sync_with_stdio(false)
#define C std::cin.tie(0)
#define Co std::cout.tie(0)
#define pll std::pair <LL, LL>
#define mp std::make_pair

typedef long long LL;
const LL N = 2e5 + 5;
LL head[N], tail[N], nxt[N], value[N], tot;
inline void add_edge(LL u, LL v, LL val) {
	tail[++tot] = v;
	value[tot] = val;
	nxt[tot] = head[u];
	head[u] = tot;
}
std::priority_queue <pll, std::vector <pll>, std::greater <pll> > q;
LL dist[N];
bool vis[N];
LL n, m, b;
inline void dijsktra(LL s){
	for(LL i = 2; i <= n; ++i) dist[i] = INT_MAX;
	q.push(mp(dist[s], s));
	vis[1] = 1;
	while (!q.empty()) {
		LL u = q.top().second; q.pop();
		if(vis[u]) continue;
		for(LL i = head[u]; ~i; i = nxt[i]) {
			LL ed = tail[i];
			if(dist[ed] > dist[u] + value[i]) {
				dist[ed] = dist[u] + value[i];	
				q.push(mp(dist[ed], ed));
			}
		}
		vis[u] = 1;
	}
} 
int main() {
	IOS; C; Co;
	std::cin >> n >> m >> b;
	while (m--) {
		LL u, v, val;
		std::cin >> u >> v >> val;
		add_edge(u, v, val);
		add_edge(v, u, val);
	}
	dijsktra(1);
	while (b--) {
		LL u, v;
		std::cin >> u >> v;
		LL ans = dist[u] + dist[v];
		std::cout << ans << '\n';
	}
	return 0;
}
2023/8/16 20:04
加载中...