25分的程序(骗分),不知第五个点为什么错了,求大神

P1600 [NOIP2016 提高组] 天天爱跑步

987445426yu @ 2017-06-18 11:42:18

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=310000;
int EdgeCnt,n,m;
struct Edge{
    int j,next;
}e[maxn];
int w[maxn],a[maxn],s[maxn],t[maxn],ans[maxn];
bool add,vis[maxn];
void addedge(int u,int v){
    int p=++EdgeCnt;
    e[p].j=v;e[p].next=a[u];a[u]=p;
//    printf("u=%d a[u]=%d\n",u,a[u]);
}
void dfs1(int s,int t,int time){
    if (vis[s])return;
//    printf("s=%d t=%d time=%d add=%d w[s]=%d\n",s,t,time,add,w[s]);
    if (s==t){
        if (w[s]==time)ans[s]++;
        add=true;return;
    }
    vis[s]=true;
    int p=a[s];
    //printf("s=%d p=%d \n",s,a[s]);
    while (p){
        //printf("%d %d \n",p,e[p].j);
        dfs1(e[p].j,t,time+1);
        p=e[p].next;
    }
    if (add && w[s]==time)ans[s]++;
}
int main(){
    //freopen("running.in","r",stdin);
    //freopen("running.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u,v);addedge(v,u);
    }
    for (int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for (int i=1;i<=m;i++)
        scanf("%d%d",&s[i],&t[i]);
    if (n<1000){
        for (int i=1;i<=m;i++){
            memset(vis,0,sizeof(vis));add=false;
            dfs1(s[i],t[i],0);
            //printf("\n\n\n\n");
        }
        for (int i=1;i<=n;i++)
            printf("%d ",ans[i]);
    }
    return 0;
}

by KEIONG @ 2017-08-09 11:02:01

你这样搜索 的正确性是严格的吗 其实我一直没有懂 是最短路径唯一 还是路径唯一


by 52dyd @ 2017-08-22 11:41:38

@KEIONG 树上的任意两点最短路径唯一啊 如果不走最短路径 那一定会重复走一条边的


|