Dijkstra求助36分
查看原帖
Dijkstra求助36分
809729
SJZ2010楼主2023/6/28 11:40

就对了后 22 个点

#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;
}

这错哪儿了???

2023/6/28 11:40
加载中...