hdu 4318 Power transmission 临接表 广搜 多校联合赛（二） 第九题
现学的临近表
广搜的过程中不断更新点剩余电量的最大值
本来想找我的参考blog的，怎么搜不到了呢！那就不好意思啦
#include<iostream>#include<cstdio>#include<queue>using namespace std;#define N 50005#define inf 0.0struct edge{ int t; int w; edge *next;}*lisk[N];int vis[N];double pa[N];void add(int u,int t,int w){ edge *tmp=new edge; tmp->t=t; tmp->w=w; tmp->next=lisk[u]; lisk[u]=tmp;}void bfs(int i,int y){ queue<int > q; q.push(i); while(!q.empty()){ int p=q.front();q.pop(); double sum=pa[p]; edge *tmp=lisk[p]; while(tmp!=NULL){ double cost=sum*(100-tmp->w)/100.0; // cout<<p<<" "<<tmp->t<<" "<<cost<<endl; if(pa[tmp->t]<cost){ q.push(tmp->t); pa[tmp->t]=cost; } tmp=tmp->next; } }}int main(){ int n,t,s,m; cout<<inf<<endl; scanf("%d",&n); for(int i=0;i<=n;i++) lisk[i]=NULL; for(int i=1;i<=n;i++){ pa[i]=inf; vis[i]=0; scanf("%d",&m); while(m--){ // cout<<t<<endl; scanf("%d%d",&t,&s); add(i,t,s); } }// edge *tmp=lisk[1];// while(tmp!=NULL){// cout<<tmp->t<<" ";// tmp=tmp->next;// }// cout<<endl;// cout<<n<<endl; int x,y; double sum; scanf("%d%d%lf",&x,&y,&sum); pa[x]=sum; vis[x]=1; bfs(x,y); if(pa[y]==inf) printf("IMPOSSIBLE!\n"); else printf("%.2lf\n",sum-pa[y]); return 0;}