[TIOJ] 1226. H遊戲

題目連結:http://tioj.infor.org/problems/1226

---

我原本以為本題就裸裸的邊作拓樸排序邊算每個點所會花到的時間就好，後來一直WA後才發現原來那樣做是錯的，因為一個點可以被走過很多次，所以有些邊要再乘以路徑數，所以還要多紀錄一下路徑數再好好算才對。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second

const int mod = 32768;
const int V = 1005;

int inDg[V], ans[V], cnt[V];
vector<PII> g[V];
vector<string> names;
bitset<V> visited;

void init(int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t;cin>>t;
	for(int _=1;_<=t;_++){
		cout<<"Game #"<<_<<'\n';
		int n, v, e;cin>>n>>v>>e;
		init(v);
		for(int i=0;i<n;i++){
			string ss;cin>>ss;
			names.PB(ss);
		}
		for(int i=0;i<e;i++){
			int st, ed, w;cin>>st>>ed>>w;
			g[st].PB({ed, w%mod});
			inDg[ed]++;
		}
		queue<int> BFS;
		BFS.push(0);
		ans[0]=0;
		cnt[0]=1;
		while(!BFS.empty()){
			auto cur = BFS.front();BFS.pop();
			for(auto i:g[cur]){
				cnt[i.FF] += cnt[cur];
				ans[i.FF] = (ans[i.FF] + ans[cur] + cnt[cur]*i.SS)%mod;
				inDg[i.FF]--;
				if(inDg[i.FF]==0) BFS.push(i.FF);
			}
		}
		for(int i=1;i<=n;i++)
			cout<<names[i-1]<<": "<<ans[i]<<'\n';
	}
	return 0;
}

void init(int v){
	for(int i=0;i<V;i++) g[i].clear();
	names.clear();
	fill(inDg, inDg+V, 0);
	visited.reset();
	fill(ans, ans+V, 0);
	fill(cnt, cnt+V, 0);
}