CCF 317号子任务 运行错误 0分

图片说明
图片说明
图片说明

#include
#include
#include
using namespace std;

const int MAXV=10010;
const int INF=0x3fffffff;
struct Node{
int v,dis; //v为边的目标顶点,dis为边权
};

struct Dis{
int dis[MAXV];
int v[MAXV];
int count;
};

vector Adj[MAXV]; //图G,Adj[u]存放从顶点u出发可以到达的所有顶点
int n; //n为顶点数,图G使用邻接表实现,MAXV为最大顶点数
int d[MAXV]; //起点到达各点的最短路径长度
bool vis[MAXV]={false}; //标记数组,vis[i]==true表示已访问。初值均为false
int k,m;

bool generator[MAXV]={false}; //是否发动机
Dis ddistance[10010]; //顶点到最近发动机的距离

void Dijkstra(int s){ //s为起点
fill(d,d+MAXV,INF); //fill函数将整个d数组赋为INF
d[s]=0; //起点s到达自身的距离为0
ddistance[s].count=0;
if(generator[s]==true){
ddistance[s].dis[ddistance[s].count]=0;
ddistance[s].v[ddistance[s].count]=s;
ddistance[s].count++;
}
if(ddistance[s].count==k) return;
for(int i=0;i<n;i++){ //循环n次
int u=-1,MIN=INF; //u使d[u]最小,MIN存放该最小的d[u]
for(int j=0;j<n;j++){ //找到未访问的顶点中d[]最小的
if(vis[j]==false&&d[j]<MIN){
u=j;
MIN=d[j];
}
}
//找到不小于INF的d[u],说明剩下的顶点和起点s不连通
if(u==-1) return;
vis[u]=true; //标记u为已访问
for(int j=0;j<Adj[u].size();j++){
int v=Adj[u][j].v; //通过邻接表直接获得u能到达的顶点v
if(vis[v]==false&&d[u]+Adj[u][j].dis<d[v]){
//如果v未访&&以u为中介点可以使d[v]更优
d[v]=d[u]+Adj[u][j].dis; //优化d[v]
if(generator[v]==true){
ddistance[s].dis[ddistance[s].count]=d[v];
ddistance[s].v[ddistance[s].count]=v;
ddistance[s].count++;
}
if(ddistance[s].count==k) return;
}
}
}
}

int main(){
scanf("%d %d %d",&n,&m,&k);
int l;
for(int i=0;i<n;i++){
scanf("%d",&l);
if(l==0) generator[i]=false;
else generator[i]=true;
}
int A,B,D;
Node node;
for(int i=0;i<m;i++){
scanf("%d %d %d",&A,&B,&D);
node.dis=D;
node.v=A-1;
Adj[B-1].push_back(node);
node.v=B-1;
Adj[A-1].push_back(node);
}
for(int i=0;i<n;i++){
Dijkstra(i);
fill(vis,vis+MAXV,false);
}
for(int i=0;i<n;i++){
int q=0;
for(int j=0;j<ddistance[i].count;j++) q=q+ddistance[i].dis[j];
printf("%d\n",q);
}
return 0;
}


1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问