Dijkstra求助36分

P4779 【模板】单源最短路径(标准版)

SJZ2010 @ 2023-06-28 11:40:53

就对了后 2 个点

#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

@鲨齿渊虹 谢谢,翻到一篇相似的帖子

已解决


|