社区讨论

求调,我老师也看不出来什么问题

P4779【模板】单源最短路径(标准版)参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lwc5qo2d
此快照首次捕获于
2024/05/18 21:41
2 年前
此快照最后确认于
2024/05/19 00:48
2 年前
查看原帖
写的迪杰斯特拉,只A了第5个点,其他WA
CPP
#include <bits/stdc++.h>
using namespace std;
long long n,m,s,id[500000],ans[500000];

struct T{
	long long you,quan;
};

vector <T> q[500005];

bool operator<(T x,T y){
	x.quan<y.quan;
}

priority_queue <T> p;

int main(){
//	freopen("P4779_1.in","r",stdin);
//	freopen("1.txt","w",stdout);
	cin >>n>>m>>s;
	for(long long i=1;i<=n;i++){
		ans[i]=0x3f3f3f3f;
	}
	
	for(long long i=1;i<=m;i++){
		long long u,v,w;
		cin >>u>>v>>w;
		q[u].push_back((T){v,w});
		id[i]=0;
	}
	p.push((T){s,0});
	ans[s]=0;
//	id[s]=1;
//	long long pd=1;
	while(p.empty()==0){
		T d=p.top();
		long long dd=d.you;
		long long ddd=d.quan;
		p.pop();
		if(id[dd]==1){
//			pd++;
			continue;
		}
		id[dd]=1;
		for(long long i=0;i<q[dd].size();i++){
			long long q1=q[dd][i].you;
			long long q2=q[dd][i].quan;
			if(ans[q1]>ans[dd]+q2){
				ans[q1]=ans[dd]+q2;
//				if(id[q1]!=1){
					p.push((T){q1,ans[q1]});
//				}
			}
		}
	}
	ans[s]=0;
	for(long long i=1;i<=n;i++){
		cout <<ans[i]<<" ";
	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...