杂物

洛谷1113

#include<cstdio>
#include<cstring>
using namespace std;
const int M=99999;int nex[M];
int head[M],to[M],cos[M];int dis[M],s=0;
int tot;int d[M*20];int vis[M],r[M];
int add(int x,int y,int z){++tot;
    nex[tot]=head[x];
    to[tot]=y;
    cos[tot]=z;
    head[x]=tot;
}int n;
int spfa(){
//  memset(dis,0,sizeof(dis));  
    dis[0]=0;
    for(int i=1;i<=n;i++)
    d[i]=0;
    vis[0]=1;
    int h=0,t=1;
    do{
        h++;
        int o=d[h];
        vis[o]=0;
        for(int i=head[o];i;i=nex[i]){
            int tmp=to[i];
        //  printf("%d  ",o);
        //  printf("%d %d %d ",dis[tmp],dis[o],i);
            if(dis[tmp]<=dis[o]+cos[i]){
                dis[tmp]=dis[o]+cos[i];
            //  printf("%d",dis[tmp]);
                if(!vis[tmp]){
                    d[++t]=tmp;
                    vis[tmp]=1;
                }
            }

        }


    }while(h<t);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x=9999;
        int a,b;
        scanf("%d%d",&a,&b);
        while(x!=0){
            scanf("%d",&x);
            if(x!=0)
            {
            add(a,x,b); 
            r[a]++;
            } 

        }if(!r[a]) s+=b;
    }
    for(int i=1;i<=n;i++){
        add(0,i,0);
    }
    spfa();
    int max1=-9999;
    for(int i=1;i<=tot;i++)
    //printf("%d  ",to[i]);
    for(int i=1;i<=n;i++)
    {
        //printf("%d",dis[i]);
        if(dis[i]>max1)
        max1=dis[i];
    }

    printf("%d",max1+s);



} 

这个题我一看就是最短路，可好像思路错的，不过能过