学步园

#include "iostream"<br /> #define M 100000000<br /> using namespace std;</p> <p>typedef struct TableEntry{</p> <p> double Dist;<br /> bool Known;<br /> }; </p> <p>TableEntry Table[101];<br /> int n,m;<br /> double Good[101],Sum;<br /> double Crate[101][101];<br /> int a,b,flag[101][101];<br /> double c;</p> <p>void InitTable()<br /> {<br /> for(int i=1;i<=n;i++)<br /> {<br /> Table[i].Dist=-1;<br /> Table[i].Known=false;<br /> }<br /> } </p> <p>void Dijkstra()<br /> {</p> <p> InitTable();<br /> Table[n].Dist=1.0;<br /> while(1)<br /> {<br /> int record=-1;<br /> double Max=-1.0;<br /> for(int i=1;i<=n;i++)<br /> {<br /> if(!Table[i].Known&&Max<Table[i].Dist)<br /> {</p> <p> Max=Table[i].Dist;<br /> record=i;<br /> }<br /> }<br /> if(record==-1)<br /> break;<br /> Table[record].Known=true;<br /> for(int i=1;i<=n;i++)<br /> {<br /> if(!Table[i].Known&&flag[record][i]&&Table[i].Dist<Max*Crate[record][i])<br /> Table[i].Dist=Max*Crate[record][i];</p> <p> } </p> <p> }<br /> for(int i=1;i<n;i++)<br /> if(Table[i].Dist!=-1)<br /> Sum+=Good[i]*Table[i].Dist;<br /> printf("%.2lf/n",Sum); </p> <p>}<br /> int main()<br /> {<br /> freopen("data.in","r",stdin);<br /> while(scanf("%d%d",&n,&m)!=EOF)<br /> {<br /> Sum=0.0;<br /> memset(flag,0,sizeof(flag));<br /> for(int i=1;i<n;i++)<br /> scanf("%lf",&Good[i]);<br /> for(int i=1;i<=m;i++)<br /> {<br /> scanf("%d%d%lf",&a,&b,&c);<br /> if((Crate[b][a]<(1-c))||!flag[b][a])<br /> {<br /> Crate[a][b]=1-c;<br /> Crate[b][a]=1-c;<br /> flag[a][b]=1;<br /> flag[b][a]=1;<br /> }<br /> }<br /> Dijkstra();<br /> }<br /> while(1);<br /> return 0;<br /> } </p> <p>