1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
| #include<bits/stdc++.h> #pragma comment(linker,"/STACK:1024000000,1024000000") using namespace std; #define rep(i,a,n) for(int i=(a);i<(n);i++) #define per(i,a,n) for(int i=(n-1);i>=(a);i--) #define fi first #define se second typedef pair <int,int> pII; typedef long long ll; const int INF = 0x3f3f3f3f; #define pb push_back const int maxn = 1e5 + 10; ll val[maxn]; ll cnt1[maxn],cnt2[maxn]; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }
int T,n,m; ll ans[maxn]; int vis[maxn]; struct node{ ll t; int id; node(){} node(ll a,int b):t(a),id(b){} bool operator<(const node&x) const{ return t > x.t; } }; void bfs(int rt,ll *cnt,vector<int>B[],vector<int>E[]){ cnt[rt] = 0; priority_queue<node > q; memset(vis,0,sizeof(vis)); int use[maxn]; memset(use,0,sizeof(use)); q.push(node(0,rt)); while(!q.empty()){ int u = q.top().id; q.pop(); for(auto bk:B[u]){ if(use[bk]) continue; use[bk] = 1; for(auto v: E[bk]){ if(cnt[u]+val[bk]>=cnt[v]) continue; cnt[v] = cnt[u] + val[bk]; q.push(node(cnt[v],v)); } } } } int main(){ #ifdef LOCAL freopen("m.in","r",stdin); #endif scanf("%d",&T); rep(test_case,1,T+1){ memset(cnt1,127,sizeof(cnt1)); memset(cnt2,127,sizeof(cnt2)); scanf("%d%d",&n,&m); vector<int> B[n+1]; vector<int> E[m+1]; rep(i,1,n+1) B[i].resize(5); rep(i,1,m+1) E[i].resize(5); rep(i,1,m+1){ val[i] = read(); int s = read(); rep(j,0,s){ int x = read(); E[i].pb(x);B[x].pb(i); } } bfs(1,cnt1,B,E); bfs(n,cnt2,B,E); ll mmin = 0xfffffff; rep(i,1,n+1){ ans[i] = max(cnt1[i],cnt2[i]); if(ans[i]<mmin) mmin=ans[i]; } if(mmin != 0xfffffff) printf("Case #%d: %lld\n",test_case,mmin); else{ printf("Case #%d: Evil John\n",test_case); continue; } int cnt = 0; ll res[maxn]; rep(i,1,n+1){ if(ans[i]==mmin) res[cnt++] = i; } rep(i,0,cnt){ printf("%d%c",res[i],i==cnt-1?'\n':' '); } } }
|