[模板]Dijkstra算法 WA0分求调

问题讨论区 提高段
81

变了CE

82

有没有人能帮一下我，告诉我一点思路
https://discourse.xinyoudui.com/t/topic/39224?u=杨北辰

83

救一下aaa

84

有人吗？

85

救我

86 
priority_queue<pair<int, int>，vector<pair<int,int> >,greater<pair<int,int> > > q;

改成小根堆！！

87

@杨浩 !!!AC,只要改堆就好了

88

一直CE

89

给我看看

90

（帖子已被作者删除）

91 
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define back_push push_back
#define mian main
using namespace std;
struct e{
	int u,v;
};
struct node{
	int p,d;
	bool operator < (const node & a)const{return a.d>d;}
};
vector<e>mp[500005];
int n,m;
int dis[100005];
bool vis[100005];
void init(){
	memset(dis,0x3f,sizeof dis);
	cin>>n>>m;
	for(int i = 1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		mp[a].back_push({b,c});
	}
}
void dijkstra(){
	priority_queue<node,vector<pair<int,int> >,greater<pair<int,int> > > q;
	dis[1]=0;
	q.push( (node){1,0} );
	while(!q.empty()){
		node temp = q.top();
		q.pop();
		int x = temp.p,d = temp.d;
		//cout<<x<<" "<<d<<endl;
		if(vis[x])continue;
		vis[x]=1;
		//cout<<mp[1].size();
		for(int i = 0;i<mp[x].size();i++){
			int tt = mp[x][i].u,ww=mp[x][i].v;
			//cout<<"!!!"<<tt<<" "<<ww<<" "<<endl;
			if(dis[tt]>dis[x]+ww){
				dis[tt]=dis[x]+ww;
				if(!vis[tt]){
					q.push( (node){tt,dis[tt]} );
				}
			}
		}
	}
}
void write(){
	for(int i = 1;i<=n;i++){
		if(dis[i] == 0x3f3f3f3f3f3f3f3f){
			cout<<"inf ";
		}else cout<<dis[i]<<" ";
	}
}
void solve(){
	init();
	dijkstra();
	write();
}
signed mian() {
	solve();
	return 0;
}
1 个赞
92

改成vector<node>

93

然后AC

94

还是CE

95

image

96 
priority_queue<node>，vector<node>,greater<node> q;

你operator因该是>啊

97

operator加上operator>

98 
bool operator>(const node &a) const { return a.d < d; }
priority_queue<node, vector<node>, greater<>> q;
99

依然CE

100

？？？