diji模板

void diji(int x){
    fill(dis,dis+n,INT_MAX);
    dis[x] = 0;
    for(int i=0;i < n;i++) pre[i] = i;
    while(1){
        int minn = INT_MAX;
        int v = -1;
        for(int i=0;i < n;i++){
            if(!vis[i]&&dis[i] < minn){
                v = i;
                minn = dis[i];
            }
        }
        if(v == -1)break;
        vis[v] = 1;
        for(int i=0;i < n;i++){
            if(!vis[i]&&cost1[i][v]!=INT_MAX&&dis[v]+cost1[i][v]<dis[i]){
                dis[i] = dis[v] + cost1[i][v];
                pre[i] = v;
            }
        }
    }
}

int main(){
    int m,s;
    cin >> n >> m >> s >> d;
    for(int i=0;i < n;i++){
        for(int j=0;j < n;j++){
            cost1[i][j] = INT_MAX;
            cost1[i][i] = 0;
        }
    }
    for(int i=0;i < m;i++){
        int x,y,a,b;
        cin >> x >> y >> a >> b;
        cost1[x][y] = a;
        cost1[y][x] = a;
        cost2[x][y] = b;
        cost2[y][x] = b;
    }
    diji(s);

    for(int i=0;i < n;i++) cout << pre[i] << " ";
    return 0;
}