SJZ2010 @ 2023-06-28 11:40:53
就对了后
#include<cstdio>
#include<cstdio>
#include<queue>
struct EDGE{
long long v,w;
};
const long long maxn=1e5+5,INF=0x3FFFFFFFFFFFF;
std::vector<EDGE> edge[maxn];
int n,m,s;
int u,v,w;
long long dis[maxn];
bool vis[maxn];
void Dijkstra(int s){
std::priority_queue< int,std::vector<int>,std::greater<int> > Q;
for(int i=1;i<=n;i++)
dis[i]=INF;
dis[s]=0;
Q.push(s);
while(!Q.empty()){
int u=Q.top();
Q.pop();
if(vis[u])
continue;
vis[u]=1;
for(int i=0;i<edge[u].size();i++){
int v=edge[u][i].v,w=edge[u][i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
Q.push(v);
}
}
}
}
int main(){
//freopen("P4779_1.in","r",stdin);
//freopen("OUT.out","w",stdout);
scanf("%d %d %d",&n,&m,&s);
while(m--){
scanf("%d %d %d",&u,&v,&w);
edge[u].push_back({v,w});
}
Dijkstra(s);
for(int i=1;i<=n;i++)
printf("%lld ",dis[i]);
return 0;
}
这错哪儿了???
by 鲨齿渊虹 @ 2023-06-28 11:51:18
你的优先队列有问题。建议你详细看下tj
by SJZ2010 @ 2023-06-28 11:53:21
@鲨齿渊虹 谢谢,翻到一篇相似的帖子
已解决