神奇的RE?为什么空间爆了?P4779的代码在这里居然过不了了?
查看原帖
神奇的RE?为什么空间爆了?P4779的代码在这里居然过不了了?
118184
In_blue楼主2020/9/27 15:17

请问各位大佬我的 Dijkstra+堆优化哪里有问题??


#include<bits/stdc++.h>
#define ll long long
#define fr(a,b,c) for(register ll a=b;a<=c;a++)
#define rf(a,b,c) for(register ll a=b;a>=c;a--)
using namespace std;
inline ll read(){
	ll s=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){s=(s<<3)+(s<<1)+(c^48);c=getchar();}
	return s*f;
}
inline void write(ll x){
	if(x<0){putchar('-');x=-x;}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
struct node{
	ll next;
	ll to;
	ll cost;
}edge[500010];
struct Node{
	ll frm;
	ll cos;
	bool operator < (const Node a) const {return a.cos<cos;}
};
ll cnt,h[10010];
ll a,b,c;
void add(){
	edge[++cnt].next=h[a];
	h[a]=cnt;
	edge[cnt].to=b;
	edge[cnt].cost=c;
}
ll n,m,dot;
ll dis[10010];bool vis[10010];
ll Dijkstra(){
	memset(dis,0x7f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	priority_queue<Node>que;
	Node t;
	t.cos=0;
	t.frm=dot;
	que.push(t);
	ll j;
	while(!que.empty()){
		t=que.top();
		que.pop();
		if(vis[t.frm])continue;
		vis[t.frm]=1;
		dis[t.frm]=t.cos;
//		cout<<t.frm<<" "<<t.cos<<endl;
		for(j=h[t.frm];j;j=edge[j].next){
			Node q;
			q.frm=edge[j].to;
			q.cos=edge[j].cost+dis[t.frm];
			if(q.cos<dis[q.frm]){
				dis[q.frm]=q.cos;
				if(!vis[q.frm])que.push(q);
			}
		}
	}
}
int main(){
	cin>>n>>m>>dot;
	fr(i,1,m){
		a=read(),b=read(),c=read();
		add();
	}
	Dijkstra();
	fr(i,1,n){
		if(vis[i])write(dis[i]),putchar(' ');
		else printf("2147483647 ");
	}
	return 0;
}
/*
5 15 5
2 5 181
1 5 98
4 2 49
3 2 262
4 3 26
2 4 192
5 1 221
2 2 254
4 4 233
1 5 44
5 4 67
4 2 214
1 1 47
1 1 118
5 4 3


221 52 29 3 0*/

蒟蒻得去上课了,如果有错请各位大佬点出

2020/9/27 15:17
加载中...