社区讨论

为什么 WA 90?

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

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@mhiztyt0
此快照首次捕获于
2025/11/03 18:24
4 个月前
此快照最后确认于
2025/11/03 18:24
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	int to,w;
	bool operator>(const node&other)const{
		return w>other.w;
	}
};
int n,m,s,dist[10005];
vector<node>g[10005]; 
void dij(){
	priority_queue<node,vector<node>,greater<node> >pq;
	pq.push({s,0});
	bool vis[10005];
	memset(vis,0,sizeof vis);
	memset(dist,0x3f,sizeof dist);
	dist[s]=0;
	while(!pq.empty()){
		node t=pq.top();
		pq.pop();
		int u=t.to;
		if(vis[u])continue;
		vis[u]=1;
		for(auto it:g[u]){
			int v=it.to,w=it.w;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				pq.push({v,dist[v]});
			}
		}
	}
}
signed main(){
	cin>>n>>m>>s;
	for(int i=1,u,v,w;i<=m;i++){
		cin>>u>>v>>w;
		g[u].push_back({v,w});
	}
	dij();
	for(int i=1;i<=n;i++)cout<<dist[i]<<' '; 
	return 0;
}

回复

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

正在加载回复...