RE0分什么情况(急,玄关)

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

chx_happy @ 2024-10-25 21:36:38

#include<bits/stdc++.h>
#define PII pair<int,int>
#define INF 2147483647
using namespace std;
vector<vector<PII>>g;
int dis[10002];
bool vis[10002];
inline int read() {
    char ch=10;
    int x=0;
    while (!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
int main() {
    int n=read(),m=read(),s=read();
    vector<PII>a;
    for(int i=1; i<=n+1; i++) g.push_back(a);
    for(int i=1; i<=m; i++) {
        int u=read(),v=read(),w=read();
        g[u].push_back({v,w});
    }
    for(int i=1; i<=n; i++) {
        if(!g[i].empty()) sort(g[i].begin(),g[i].end());
    }
    priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push({0,s});
    dis[s]=0;
    fill(dis+1,dis+1+n,INF);
    while(!q.empty()) {
        PII no=q.top();
        int u=no.second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto it:g[u]) {
            int v=it.first,w=it.second;
            if(no.first+w<dis[v]) {
                dis[v]=no.first+w;
                q.push({dis[v],v});
            }
        }
    }
    for(int i=1; i<=n; i++) {
        if(i==s) {
            cout<<0<<' ';
            continue;
        } else {
            cout<<dis[i]<<' ';
        }
    }
    return 0;
}

by chx_happy @ 2024-10-25 21:37:18

蒻化版过了


by wuyuxuan12345678 @ 2024-10-25 21:40:12

数组开小了,再多加点 @chx_happy


by chx_happy @ 2024-10-25 21:41:06

@wuyuxuan12345678 已经过了,谢谢(互关)


by wuyuxuan12345678 @ 2024-10-25 21:41:36


|