TIOJ 1226 H遊戲 [Graph]

poao899    3772K    312MS    G++     1.07K     2010-03-27 17:05:15                                        .




題目是說   給一張DAG，問你從A到B所有走法的路徑和%32768

V<=1000, E<=10^6

































就topological sort + DP



//*********************************

#include<stdio.h>
#define MODE 32768
char name[100][25];
int stamp[1010],ttime,cost[1010],dp[1010],t,n,v,e,x,y,z;
bool visited[1010];
struct edge{
    int j,cost;
    edge *next;
}E[1000010],*V[1010];
void dfs(int n){
    visited[n]=1;
    for(edge *p=V[n]; p; p=p->next)
        if(!visited[p->j])
            dfs(p->j);
    stamp[ttime++]=n;
}
int main(){
    scanf("%d\n",&t);
    for(int cnt=1;cnt<=t;cnt++){
        printf("Game #%d\n",cnt);
        //init
        scanf("%d%d%d\n",&n,&v,&e);
        for(int i=0;i<v;i++){
            cost[i]=dp[i]=visited[i]=stamp[i]=0;
            V[i]=NULL;
        }
        dp[0]=1;
        ttime=0;
        //input
        for(int i=0;i<n;i++)
            gets(name[i]);
        for(int i=0;i<e;i++){
            //printf("i=%d e=%d\n",i,e);
            scanf("%d%d%d",&x,&y,&z);
            edge *p=&E[i],*q=V[x];
            V[x]=p; p->j=y; p->next=q; p->cost=z;
        }
        //time stamp
        dfs(0);
        //dp
        for(int i=ttime-1;i>=0;i--){
            int now=stamp[i];
            for(edge *p=V[now]; p; p=p->next){
                cost[p->j]+=cost[now]+ p->cost*dp[now];
                cost[p->j]%=MODE;
                dp[p->j]+=dp[now];
            }
        }
        for(int i=0;i<n;i++)
            printf("%s: %d\n",name[i],cost[i+1]);
    }
}