社区讨论

为什么我用Dijkstra过了。看自己以前写的玄学代码看不懂了

P1550[USACO08OCT] Watering Hole G参与者 6已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mi6vdx29
此快照首次捕获于
2025/11/20 11:26
4 个月前
此快照最后确认于
2025/11/20 11:26
4 个月前
查看原帖
CPP
#include<iostream>

#define SIZE 305
#define INF 9999999

using namespace std;

int n,a;
struct graph{
    int p[SIZE][SIZE];
    bool vis[SIZE];
    int w[SIZE],d[SIZE];
    void clr(){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)p[i][j]=INF;
            p[i][i]=0;
            d[i]=INF;
        }
    }
    void addpath(int from,int to,int val){
        p[from][to]=val;
    }
    int start(){
        int res=0,mn=INF;
        for(int i=1;i<=n;i++){
            if(w[i]<mn)res=i,mn=w[i];
        }
        return res;
    }
    int dijk(int st){
        int res=0;
        d[st]=w[st];
        for(int i=1;i<=n;i++){
            int now,mn=INF;
            for(int j=1;j<=n;j++){
                if(!vis[j]&&mn>d[j])mn=d[j],now=j;
            }
            vis[now]=true;
            for(int j=1;j<=n;j++){
                if(!vis[j]){
                    if(d[j]>w[j])d[j]=w[j];
                    if(d[j]>p[now][j])d[j]=p[now][j];
                }
            }
        }
        for(int i=1;i<=n;i++)res+=d[i];
        return res;
    }
};

graph g;

int main(){
    cin>>n;
    g.clr();
    for(int i=1;i<=n;i++)cin>>g.w[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a;
            g.addpath(i,j,a);
        }
    }
    cout<<g.dijk(g.start());
    return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...