MoXiaodu @ 2019-11-08 17:24:05
Rt(希望这次不要被无视qwq)
#include<bits/stdc++.h>
using namespace std;
struct pa{
int ha,dis,ne;
}q[500001];
struct note{
int dis,pos;
}d[500001];
int line_cd,cnt=0,n,m,s,h[100001],v[100001],dis[100001],Q;
void push_d(int a,int bh){
line_cd++;
d[line_cd].dis=a;
d[line_cd].pos=bh;
if(line_cd==1)
return;
int dq=line_cd;
int next=line_cd/2;
while(next>=1){
if(d[dq].dis<d[next].dis){
swap(d[dq],d[next]);
dq=next;
next/=2;
}
else return;
}
}
note top_pop_d(){
int res=d[1].dis;
int bh=d[1].pos;
d[1]=d[line_cd];
line_cd--;
if(line_cd==1)return note{res,bh};
int dq=1;
int next=2;
while(next<=line_cd){
if(d[next].dis>d[next+1].dis)next++;
if(d[dq].dis>d[next].dis){
swap(d[next],d[dq]);
dq=next;
next*=2;
}
else return note{res,bh};
}
return note{res,bh};
}
void in(int x,int y,int z){
cnt+=1;
q[cnt].dis=z;
q[cnt].ne=y;
q[cnt].ha=h[x];
h[x]=cnt;
}
void djstl(){
dis[s]=0;
push_d(0,s);
while(line_cd){
note tp=top_pop_d();
int x=tp.pos,d=tp.dis;
if(v[x])continue;
v[x]=1;
for(int i=h[x];i;i=q[i].ha){
int y=q[i].ne;
if(dis[y]>max(dis[x],q[i].dis)){
dis[y]=max(dis[x],q[i].dis);
if(!v[y]){
push_d(dis[y],y);
}
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&Q);
int sss=0;
while(n&&m&&Q){
sss++;
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
in(x,y,z);in(y,x,z);
}
cout<<"Case #"<<sss<<endl;
for(int i=1;i<=Q;i++){
scanf("%d",&s);
int c;scanf("%d",&c);
djstl();
if(v[c])
cout<<dis[c]<<endl;
else cout<<"no path\n";
memset(dis,0x3f,sizeof(dis));memset(d,0,sizeof(d));memset(v,0,sizeof(v));
}
scanf("%d%d%d",&n,&m,&Q);
memset(h,0,sizeof(h));
memset(q,0,sizeof(q));
cnt=0;
}
return 0;
}
by 爷,无限霸气 @ 2019-11-08 17:26:31
@陌言·pzt 其实说女孩子更好
orz pzt
%%%pzt
by mengzhi @ 2019-11-08 17:29:13
您怎么会错呢
一定是题错了~~
by MoXiaodu @ 2019-11-08 17:33:22
@mengzhi QAQ
by GossWandering @ 2019-11-08 17:36:03
我又遇到了个红名巨佬装弱的
by Ja50nY0un9_as_AgNO3 @ 2021-08-16 20:05:29
然而说是女孩子会被禁言啊。。。