[TIOJ 1226] H遊戲

作法：

一開始又理解錯題目意思了......總之這題要求的就是「從 0 到某些點的所有走法的路徑長度總和」，而很明顯如果圖裡有環就噴射了，但題目沒有講OAO ( 當然測資是沒有環的 )。

所以就可以簡單對每個終點DP了，只要記錄每個點到特定一個終點有幾種走法，和所有走法的路徑總和就好了。但我第一次傳上去 WA 了，後來發現原因竟然是「終點可能有連出一些邊」！！！ 這不合理阿，為什麼到了一個女主角的結局之後經過一些事件還能再到另一個女主角的結局，不是應該就結束了嗎=口=

code :

#include<bits/stdc++.h>
#define MOD 32768
using namespace std;
const int maxn=2000+10 ;
struct P{int to,dis;};
 
int num[maxn][200+10] ;
int d[maxn][200+10],m,n ;
bool vis[maxn] ;
vector<P> v[maxn] ;
char name[200+10][200] ;
 
void dp(int x)
{
    if(vis[x]) return ;
    vis[x]=1 ;
    for(auto j : v[x])
    {
        dp(j.to) ;
        for(int i=1;i<=m;i++)
        {
            num[x][i]=(num[x][i]+num[j.to][i])%MOD ;
            d[x][i]=(d[x][i]+num[j.to][i]*j.dis+d[j.to][i])%MOD ;
        }
    }
    if(x>=1 && x<=m) num[x][x]++ ;
}
 
main()
{
    int T,tc=0 ; scanf("%d",&T) ;
    while(T--)
    {
        int x ; scanf("%d%d%d",&m,&n,&x) ;
        for(int i=0;i<maxn;i++) v[i].clear() ;
        for(int i=1;i<=m;i++) scanf("%s",name[i]) ;
        while(x--)
        {
            int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
            dis%=MOD ;
            v[x].push_back((P){y,dis}) ;
        }
        memset(vis,0,sizeof(vis)) ;
        memset(d,0,sizeof(d)) ;
        memset(num,0,sizeof(num)) ;
        dp(0) ;
 
        printf("Game #%d\n",++tc) ;
        for(int i=1;i<=m;i++) printf("%s: %d\n",name[i],d[0][i]) ;
    }
}