hdu1839之二分+邻接表+Dijkstra+队列优化 (二)
oid InsertEdge(int u,int v,int &c,int &t){
edge[size]=Edge(v,c,t,head[u]);//头插法
head[u]=size++;
}
inline bool Dijkstra(int s,int t,int c,int T){
for(int i=1;i<=n;++i)mark[i]=false,dist[i]=INF;
dist[s]=0,mark[s]=true;
priority_queue< mp,vector,greater >q;
mp oq;
q.push(mp(0,s));
while(!q.empty()){
oq=q.top();
q.pop();
if(oq.first>T)return false;
if(oq.second == t)return dist[t];//dist[t]<=T;
mark[oq.second]=true;
for(int i=head[oq.second];i != -1;i=edge[i].next){
int v=edge[i].v;
if(mark[v] || edge[i].c
>num;
while(num--){
scanf("%d%d%d",&n,&m,&t);
Init(n);
for(int i=0;i>1;
if(Dijkstra(1,n,s[mid],t))left=mid+1;
else right=mid-1;
}
printf("%d\n",s[right]);
}
return 0;
}