AC code:
#include<iostream> #include<stdio.h> #include<queue> #include<iomanip> #include<string> #include<cstring> using namespace std; #define N 50005 struct Edgenode { int v,next; double cost; }Edge[N*55]; int edgenumber,head[N]; int visited[N]; double Sum[N]; void SAFA(int s,int t,int total); void addedge(int i,int v1,double value) { Edge[edgenumber].v=v1; Edge[edgenumber].cost=value; Edge[edgenumber].next=head[i]; head[i]=edgenumber++; } int main() { int n,i,j,k,value,s,t,total; while(scanf("%d",&n)!=EOF) { memset(head,-1,sizeof(head)); edgenumber=0; for(i=1;i<=n;i++) { cin>>j; while(j--) { cin>>k>>value; addedge(i,k,value/100.00); } } cin>>s>>t>>total; for(int q=0;q<=n;++q) { visited[q]=0; Sum[q]=total;} SAFA(s,t,total); if(Sum[t]>=total) cout<<"IMPOSSIBLE!"<<endl; else printf("%.2lf\n",Sum[t]); } return 0; } void SAFA(int s,int t,int total) { queue<int> q; q.push(s); double temp; int i,j,k; Sum[s]=0; visited[s]=true; while(!q.empty()) { i=q.front(); q.pop(); for(j=head[i];j!=-1;j=Edge[j].next) { k=Edge[j].v; temp=Sum[i]+(total-Sum[i])*Edge[j].cost; if(Sum[k]<=temp) continue; Sum[k]=temp; if(visited[k]) continue; q.push(k); visited[k]=1; } visited[i]=0; } }