为什么不用前向星呢?
by XLost @ 2019-07-20 08:38:22
我明白了,不能用i,因为i把父亲也算上了
修改后的代码
```
//听取wa声一片
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#define noip2019 RP++
#define ll long long
using namespace std;
inline ll read()
{
ll f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
ll n,s,a,b,x[500100],ans;
struct node
{
ll to,dis;
}cur;
vector<node> v[500100];
bool book[500100];
void dfs(ll k)
{
book[k]=1;
//printf("%d",k);
int cnt=0;
for(int i=0;i<v[k].size() ;i++)
{
node cur1=v[k][i];
ll to=cur1.to ,dis=cur1.dis ;
if(!book[to])
{
// printf("%d %d\n",k,x[k]);
dfs(to);
//printf("%d %d %d\n",cur1.to ,x[cur1.to],cur1.dis );
if(x[k]<x[to]+dis)
{
ans+=(x[to]+dis -x[k])*cnt;
x[k]=x[to]+dis;
}
if(x[to]+dis<x[k])
{
ans+=(x[k]-x[to]-dis);
}
cnt++;
}
}
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
n=read();
s=read();
for(int i=1;i<n;i++)
{
a=read();
b=read();
cur.dis =read();
cur.to =b;
v[a].push_back(cur);
cur.to =a;
v[b].push_back(cur);
}
dfs(s);
printf("%lld",ans);
return 0;
}
```
by sunxiaofan @ 2019-07-20 08:39:30
@[Lost_person](/space/show?uid=182022)
用vector写比较短
感谢您
by sunxiaofan @ 2019-07-20 08:40:17
QWQ
by XLost @ 2019-07-20 08:42:06