#70pntsTLE dijstra 求优化#
查看原帖
#70pntsTLE dijstra 求优化#
514936
EllinY楼主2022/12/8 17:44

堆优化+dijkstra 怎么没过 求助大佬

#include<bits/stdc++.h>
using namespace std;
#define PII pair<long long,int>
int n,m,start;
int to[200001],nex[200001],last[100001],cnt;
long long len[200001],dis[100001];
bool vis[100001];
priority_queue<PII,vector<PII>,greater<PII> > q;
void add(int a,int b,int c){
	cnt++;
	to[cnt]=b;
	len[cnt]=c;
	nex[cnt]=last[a];
	last[a]=cnt;
}
int main(){
	scanf("%d %d %d",&n,&m,&start);
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		dis[u]=dis[v]=INT_MAX;
		add(u,v,w);
	}
	dis[start]=0;
	PII t;
	t.first=0,t.second=start;
	q.push(t);
	while(!q.empty()){
		t=q.top();
		q.pop();
		int point=t.second,weigh=t.first;
		if(vis[point]) continue;
		vis[point]=1;
		int i=last[point];
		while(i!=0){
			int go=to[i];
			if(dis[go]>dis[point]+len[i]){
				dis[go]=dis[point]+len[i];
				t.first=dis[go],t.second=go;
				q.push(t);
			}
			i=nex[i];
		}
	}
	for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
	return 0;
} 

Thanks♪(・ω・)ノ

2022/12/8 17:44
加载中...