萌新刚学Dij板子求调,WA52pts只对点2,5,6
查看原帖
萌新刚学Dij板子求调,WA52pts只对点2,5,6
552298
Greenzhe楼主2022/9/3 09:10

建的是有向边,数组也没有开小,求问各位大佬哪里写挂了

#include <bits/stdc++.h>
using namespace std;

int n,m,s;
int dis[100005];
bool vis[100005];
struct edge{
	int v,w; //v终点,w权值
};
vector<edge> rel[100005]; 
const int INF=0x3f3f3f3f;

void dijkstra();

int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		rel[u].push_back({v,w});
	}
	memset(dis,0x3f,sizeof(dis));
	dijkstra();
	for(int i=1;i<=n;++i)
		printf("%d ",dis[i]);
	printf("\n");
	return 0;
}
struct cmp{
	bool operator()(int a,int b){
		return dis[a]>dis[b];
	}
}; //自定义比较仿函数,用于小根堆
void dijkstra(){
	priority_queue<int,vector<int>,cmp> q;
	dis[s]=0;
	vis[s]=true;
	q.push(s);
	while(!q.empty()){
		int x=q.top();
		q.pop();
		for(int i=0;i<rel[x].size();++i){
			int y=rel[x][i].v;
			if(dis[x]+rel[x][i].w<dis[y]){
				dis[y]=dis[x]+rel[x][i].w;
				if(!vis[y]){
					vis[y]=true;
					q.push(y);
				}
			}
		}
	}
}
2022/9/3 09:10
加载中...