题意：有n个点，m个点集，每个点集中有e[i]个点，同一点集的点互相之间到达需要t[i]单位的时间，求min(max(dis(1,i),dis(i,n)))，i属于[1,n]
输出最小值并増序输出所有使答案取到最小值的i，无解输出Evil John
n<=1e5,1<=t[i]<=1e9,sigma e[i]<=1e6
思路：出烂了的裂点最短路
对于每个点集另外裂一个点id，设该点集中的点为a[i]
a[i]——>id 长度为t[i]
id——>a[i] 长度为0
以1和n为起点跑两遍dijkstra+堆
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 typedef long long ll; 13 typedef unsigned int uint; 14 typedef unsigned long long ull; 15 typedef pair<int,int> PII; 16 typedef vector<int> VI; 17 #define fi first 18 #define se second 19 #define MP make_pair 20 #define N 1200000 21 #define M 2200000 22 #define MOD 1000000007 23 #define eps 1e-8 24 #define pi acos(-1) 25 #define oo 1ll<<60 26 priority_queue<pair<ll,int> > q; 27 28 ll dis1[N],dis2[N]; 29 int head[N],vet[M],len[M],nxt[M],vis[N],c[N],id,tot; 30 31 int add(int a,int b,int c) 32 { 33 //printf("%d %d %d ",a,b,c); 34 nxt[++tot]=head[a]; 35 vet[tot]=b; 36 len[tot]=c; 37 head[a]=tot; 38 } 39 40 ll min(ll x,ll y) 41 { 42 if(x<y) return x; 43 return y; 44 } 45 46 ll max(ll x,ll y) 47 { 48 if(x>y) return x; 49 return y; 50 } 51 52 int main() 53 { 54 freopen("M.in","r",stdin); 55 freopen("M.out","w",stdout); 56 int cas; 57 scanf("%d",&cas); 58 for(int t=1;t<=cas;t++) 59 { 60 int n,m; 61 scanf("%d%d",&n,&m); 62 for(int i=1;i<=id;i++) head[i]=dis1[i]=dis2[i]=0; 63 tot=0; 64 id=n; 65 for(int i=1;i<=m;i++) 66 { 67 int x,y; 68 scanf("%d%d",&x,&y); 69 id++; 70 for(int j=1;j<=y;j++) 71 { 72 int z; 73 scanf("%d",&z); 74 add(z,id,x); 75 add(id,z,0); 76 } 77 } 78 for(int i=1;i<=id;i++) 79 { 80 vis[i]=0; 81 dis1[i]=oo; 82 } 83 //for(int i=1;i<=id;i++) printf("%d %lld ",i,dis1[i]); 84 q.push(MP(0,1)); dis1[1]=0; 85 while(!q.empty()) 86 { 87 int u=q.top().se; 88 q.pop(); 89 if(vis[u]) continue; 90 vis[u]=1; 91 int e=head[u]; 92 while(e) 93 { 94 int v=vet[e]; 95 if(dis1[u]+len[e]<dis1[v]) 96 { 97 dis1[v]=dis1[u]+len[e]; 98 q.push(MP(-dis1[v],v)); 99 } 100 e=nxt[e]; 101 } 102 } 103 104 for(int i=1;i<=id;i++) 105 { 106 vis[i]=0; 107 dis2[i]=oo; 108 } 109 q.push(MP(0,n)); dis2[n]=0; 110 while(!q.empty()) 111 { 112 int u=q.top().se; 113 q.pop(); 114 if(vis[u]) continue; 115 vis[u]=1; 116 int e=head[u]; 117 while(e) 118 { 119 int v=vet[e]; 120 if(dis2[u]+len[e]<dis2[v]) 121 { 122 dis2[v]=dis2[u]+len[e]; 123 q.push(MP(-dis2[v],v)); 124 } 125 e=nxt[e]; 126 } 127 } 128 //for(int i=1;i<=id;i++) printf("%d %lld %lld ",i,dis1[i],dis2[i]); 129 ll mn=oo; 130 for(int i=1;i<=n;i++) mn=min(mn,max(dis1[i],dis2[i])); 131 // printf("mn=%lld ",mn); 132 printf("Case #%d: ",t); 133 if(mn==oo) printf("Evil John "); 134 else 135 { 136 int ans=0; 137 for(int i=1;i<=n;i++) 138 if(max(dis1[i],dis2[i])==mn) c[++ans]=i; 139 printf("%lld ",mn); 140 for(int i=1;i<=ans-1;i++) printf("%d ",c[i]); 141 printf("%d ",c[ans]); 142 } 143 } 144 return 0; 145 } 146 147 148