评测记录

#include<bits/stdc++.h>
using namespace std;
int n,s,t;
const int MAXN=300005;
inline int read()
{
   int x=0;
   char ch=getchar();
   while(!isdigit(ch))
       ch=getchar();
   while(isdigit(ch))
       x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
   return x;
}
struct node 
{
   int v,w;
};
vector<node>e[MAXN];
long long sdis[MAXN],tdis[MAXN],ans;
int u[MAXN],v[MAXN],w[MAXN],from[MAXN];
void sdfs(int x,int fa)
{
      
   for(int i=0;i<e[x].size();i++)
       if(e[x][i].v!=fa)
       {
           sdis[e[x][i].v]=sdis[x]+e[x][i].w;
           from[e[x][i].v]=x;
           sdfs(e[x][i].v,x);
       }
}
void tdfs(int x,int fa)
{
      
   for(int i=0;i<e[x].size();i++)
       if(e[x][i].v!=fa)
       {
           tdis[e[x][i].v]=tdis[x]+e[x][i].w;
           if(tdis[e[x][i].v]<=sdis[e[x][i].v])
               from[e[x][i].v]=x;
           tdfs(e[x][i].v,x);
       }
}
int main()
{
   n=read(),s=read(),t=read();
   for(int i=1;i<=n-1;i++)
   {
       u[i]=read(),v[i]=read(),w[i]=read();
       e[u[i]].push_back((node){v[i],w[i]});
       e[v[i]].push_back((node){u[i],w[i]});
   }
   sdfs(s,0);
   tdfs(t,0);
   for(int i=1;i<=n;i++)
       ans+=min(sdis[i],tdis[i]);
   printf("%lld\n",ans);
   for(int i=1;i<=n-1;i++)
   {
       if(u[i]==s||u[i]==t)
           printf("2");
       else if(v[i]==s||v[i]==t)
           printf("1");
       else if(from[u[i]]==v[i])
           printf("1");
       else if(from[v[i]]==u[i])
           printf("2");
       else
           printf("0");
   }
   printf("\n");
   return 0;
}

求助各位dalao，谢谢