睡不着kkk 2019-09-14 17:01 采纳率: 50%
浏览 442

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条回答 默认 最新

  • zqbnqsdsmd 2019-09-14 21:18
    关注
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题