自己瞎写的Dijkstra堆优化 为啥CE
查看原帖
自己瞎写的Dijkstra堆优化 为啥CE
1412938
A7F3jK9pR0xf_楼主2024/8/12 19:00

本地IDE过了,用的是DEV-C++,编译器是-std=c++14

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5+10, M = 2e5+10;
const int INF = 0x3f3f3f3f;
int dis[N], n, m;
bool tag[N];
vector<pair<int, int> >g[N];
struct node
{
	int id, w;
	friend operator < (const node &n1, const node &n2)
	{
		return n1.w > n2.w;	
	}	
};
priority_queue<node>q; // 堆优化 
inline void Dijkstra(int s) // O(n log n) 
{
	for(int i = 1;i <= n;++i)
	{
		dis[i] = INF;
		tag[i] = 0;
	}
	dis[s] = 0;
	for(int i = 1;i <= n;++i)
		q.push((node){i, dis[i]});
	int cnt = 0;
	while(cnt < n)
	{
		node cur;
		while(q.size())
		{
			cur = q.top();
			q.pop();
			if(cur.w == dis[cur.id] && !tag[cur.id])
				break;
		}
		tag[cur.id] = 1;
		cnt++;
		for(auto v : g[cur.id])
		{
			if(!tag[v.first])
			{
				dis[v.first] = min(dis[v.first], dis[cur.id]+v.second);
				q.push((node){v.first, dis[v.first]});
			}
		}	
	} 
} 
int main()
{
	int s, u, v, w;
	scanf("%d%d%d", &n, &m, &s);
	while(m--)
	{
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back(make_pair(v, w));
	}
	Dijkstra(s);
	for(int i = 1;i <= n;++i)
		cout << dis[i] << " ";
	return 0;
}

2024/8/12 19:00
加载中...