社区讨论
为什么我用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 条回复,欢迎继续交流。
正在加载回复...