84pts TLE求调
查看原帖
84pts TLE求调
1408395
_lxc__楼主2024/12/14 18:42

dijkstra 算法+堆优化理论复杂度 0(m×logn)0(m\times logn),不知道为什么会超时

#include<bits/stdc++.h> 
using namespace std;
const int N=1e5+10;
int n,m,s,dis[N],vis[N];
struct node{
	int v,w;
};
struct Node{
	int val,id;
};
vector<node> adj[N];
bool operator <(const Node &x,const Node &y){
	return x.val>y.val;
}
void solve(int s){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	priority_queue<Node> pq;
	pq.push({0,s});
	while(pq.size()){
		Node t=pq.top();
		pq.pop();
		int u=t.id;
		vis[u]=1;
		for(auto x:adj[u]){
			int v=x.v,w=x.w;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					pq.push({dis[v],v});
				}
			}
		}
	}
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(register int i=1;i<=m;i++){
    	int u,v,w;
    	scanf("%d%d%d",&u,&v,&w);
    	adj[u].push_back({v,w});
	}
	solve(s);
	for(register int i=1;i<=n;i++){
		printf("%d ",dis[i]);
	}
    return 0;
}
2024/12/14 18:42
加载中...