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;}