题解 P2784 【化学1（chem1）- 化学合成】

浮点数版单源最长路，很容易想到spfa。把模板改一改即可。 ``` #include<bits/stdc++.h> #define db double using namespace std; queue<int>que;int sta,end,fir[5005];bool vis[5005];db dis[5005];struct STR{db val;int next,to;}edge[2000005]; void add(int u,int v,db val,int pos){ edge[pos].next=fir[u];fir[u]=pos;edge[pos].val=val;edge[pos].to=v; } void spfa(){ vis[sta]=dis[sta]=1;que.push(sta); while(!que.empty()){ int fr=que.front(); for(int i=fir[fr];i;i=edge[i].next) if(dis[edge[i].to]<edge[i].val*dis[fr]){ dis[edge[i].to]=edge[i].val*dis[fr]; if(!vis[edge[i].to]){ vis[edge[i].to]=1;que.push(edge[i].to); } } vis[fr]=0;que.pop(); } } int main(){ int n,m;scanf("%d%d%d%d",&n,&m,&sta,&end); for(int i=1;i<=m;i++){ int u,v;db turn;scanf("%d%d%lf",&u,&v,&turn);add(u,v,turn,i); } spfa();dis[end]?printf("%.4lf",dis[end]):printf("orz"); return 0; } ```