社区讨论

SPFA求助40pts

P3371【模板】单源最短路径(弱化版)参与者 7已保存回复 10

讨论操作

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

当前回复
10 条
当前快照
1 份
快照标识符
@loddz022
此快照首次捕获于
2023/10/31 05:02
2 年前
此快照最后确认于
2023/11/06 20:22
2 年前
查看原帖
AC:5;TLE:4;WA:1\text{AC:5;TLE:4;WA:1}
具体测评结果看
代码:
CPP
#include<bits/stdc++.h>
int n,m,s,Edgecnt;
int head[10010],edge[10010];
int nxt[500010],to[500010];
int dis[10010],f[10010];
queue<int> q;
void add(int u,int v,int w){
	Edgecnt++;
	to[Edgecnt]=v,edge[Edgecnt]=w;
	nxt[Edgecnt]=head[u],head[u]=Edgecnt;
}
void spfa(){
	dis[s]=0;f[s]=1;q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		v[x]=0;
		for(int i=head[x];i;i=nxt[i]){
			int tmp=to[i],val=edge[i];
			if(dis[tmp]+val<dis[x]){
				dis[x]=dis[tmp]+val;
				if(!vis[tmp]){
					q.push(y);
					v[y]=1;
				}
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int from,to,val;
		cin>>from>>to>>val;
		add(from,to,val);
	}
	spfa();
	for(int i=1;i<=n;i++) cout<<dis[i]<<endl;
	return 0;
}
Thx

回复

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

正在加载回复...