社区讨论
为什么 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 条回复,欢迎继续交流。
正在加载回复...