/* http://acm.nyist.net/JudgeOnline/problem.php?pid=679 贪婪的商店 最短路 或者 树形dp 很裸的树形dp,要买一件东西,需要再买某些物品,问最少需要花多少钱才能买到那件东西 */ #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <cctype> #include <set> #include <queue> #include <stack> #include <string> using namespace std; #define CLR(c,v) (memset(c,v,sizeof(c))) const int INF = (1<<29); const int inf = -(1<<20); template < typename _T> _T Min(_T a,_T b){ return (a<b)?(a):(b); } int dp[10000]; int v[1005]; bool vis[1005]; vector <int > s[1005]; void dfs(int cur){ if(vis[cur])return; int size = s[cur].size(); if(size == 0){ dp[cur] = v[cur];return ; } for(int i = 0 ; i < size ; i++){ int child = s[cur][i]; dfs(child); vis[child] = true; dp[cur] = Min(dp[cur] , dp[child] + v[cur]); } } int main(){ freopen("in.txt","r",stdin); int Ncase;cin >> Ncase;int cnt = 0; while(Ncase -- ){ int n,m,p; cin >> n >> m >> p; CLR(vis,0); for(int i = 1 ; i <= n ; i ++) dp[i] = INF; for(int i = 1 ; i <= n ; i++) scanf("%d",&v[i]); for(int i = 0 ; i< m ; i++){ int a,b; cin >> a >> b; s[a].push_back(b); } dfs(p); printf("Case #%d: %d\n",++cnt , dp[p]); for(int i = 1 ; i <= n ; i ++) s[i].clear(); } return 0; }