讨论 / 树状结构?
沧海一声喵 2018-02-26 00:01:45
点我顶贴 收藏 删除
题目中说的树状结构一定是二叉树吗?
#1 沧海一声喵@2018-02-26 00:45:55
回复 删除
#include <cstdio>

#include <cstring>

using namespace std;

typedef struct node{

int pre,d,num,c[101],flag[101];

}node;

node v[101];int dis=0,cur=0;

int main(){

int i,j,n,p,s,t,l,min;

scanf("%d%d",&n,&p);

for(i=0;i<n;i++){

v[i].d=v[i].pre=v[i].num=0;

memset(v[i].c,0,sizeof(v[i].c));memset(v[i].flag,0,sizeof(v[i].flag));}

for(i=2;i<=n;i++){

scanf("%d%d%d",&s,&t,&l);

v[t].pre=s;v[t].d=l;v[s].num++;

v[s].c[v[s].num]=t;}

while(1){

if(cur==p) break;

for(i=1;i<=v[cur].num;i++)

if(!v[cur].flag[i]) break;

if(i>v[cur].num){

dis+=v[cur].d;cur=v[cur].pre;}

else{

for(min=10005,i=1;i<=v[cur].num;i++){

s=v[cur].c[i];

if(!v[cur].flag[i]&&(v[s].d<min||(v[s].d==min&&s==p))){

min=v[s].d;t=i;}}

v[cur].flag[t]=1;

cur=v[cur].c[t];dis+=min;}}

printf("%d",dis);

return 0;}

查看更多回复
提交回复