编译错误求调

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

1CR_wait_ME @ 2023-03-10 17:42:50

#include <iostream>
#define MAXNUM 1000000001
using namespace std;

int n, m;
int s;//起点 

int graph[100001][100001];

int distance_[100001];
int SV[100001];
int S[100001];

int SVsize;

void Dij(){
//初始化
    for(int i = 1; i<=n; i++){
        distance_[i] = MAXNUM;
    } 
    distance_[s] = 0;
    SV[s] = 1;
    SVsize++;
//算法部分
    int newnode;
    int minl;
    while(1){
    //拓展S集
        if(!SVsize) return;
        minl = MAXNUM;
        for(int i = 1; i<=n; i++){
            if(SV[i]){
                if(distance_[i]<minl){
                    newnode = i;
                    minl = distance_[i];
                }
            }
        } 
        S[newnode] = 1;
        SV[newnode] = 0;
        SVsize--;
    //更新标签
        for(int i = 1; i<=n; i++){
            if(graph[newnode][i]&&!S[i]&&distance_[newnode]+graph[newnode][i]<distance_[i]){
                if(distance_[i]==MAXNUM){
                    SV[i] = 1;
                    SVsize++;
                }
                distance_[i] = distance_[newnode]+graph[newnode][i];
            }
        } 
    } 
    return;
}

int main(){
    cin >> n >> m >> s;
    int u, v, w;
    for(int i = 1; i<=m; i++){
        cin >> u >> v >> w;
        graph[u][v] = w;
    }
    Dij();
    for(int i = 1; i<=n; i++){
        cout << distance_[i] << " ";
    }
    return 0;
} 

在本地测,提示源文件未编译,交上去就ME了 人快气炸了,哪位lalao帮忙看看 谢谢


by w9095 @ 2023-03-10 17:58:04

@running_icd 数组太大了,请换更好的存图方式。


by 1CR_wait_ME @ 2023-03-10 18:01:18

@w9095 所以,用……链式前向星?


by w9095 @ 2023-03-10 18:03:22

@running_icd 没错,这里 的链式前向星


by 1CR_wait_ME @ 2023-03-23 20:45:21

@w9095 谢谢!


|