Dijkstra set版通不过
查看原帖
Dijkstra set版通不过
359067
IWAN楼主2021/10/11 22:25
#include<bits/stdc++.h>
using namespace std;
struct edge{
	int to,len;
}tmp;
struct node{
	int dis,to;
	bool operator<(const node &x)const{
		return dis<x.dis;
	}
};
vector<edge>g[100010];
set<node>s;
int n,m,o,dis[100010],a,b,len,now;
void Dijkstra(int start){
	memset(dis,100,sizeof(dis));
	dis[start]=0;
	for(s.insert(node{0,start});s.size();){
		now=s.begin()->to;s.erase(s.begin());
		for(int i=0;i<g[now].size();i++){
			tmp=g[now][i];
			if(dis[tmp.to]>dis[now]+tmp.len){
				s.erase(node{dis[tmp.to],tmp.to});
				dis[tmp.to]=dis[now]+tmp.len;
				s.insert(node{dis[tmp.to],tmp.to});
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&o);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&len);
		g[a].push_back(edge{b,len});
	}
	Dijkstra(o);
	for(int i=1;i<=n;i++){
		printf("%d ",dis[i]);
	}
	return 0;
}

请问为什么程序通不过,我是用set实现二叉堆优化dijkstra的

2021/10/11 22:25
加载中...