题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2098
spfa顺便判负环…非常非常水，所以最开始想粘个代码就跑…结果没找到，要是有有缘人看到了这篇题解……
那么你就找到了可以粘的代码=.=
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<bits/stdc++.h> #define maxn 2020 #define pb push_back #define db double using namespace std; struct node{ int to; db val; node(int x,db y){to=x,val=y;} node(){} }; int n,m,A,B; int num[maxn]; db V,dis[maxn]; vector<node>go[maxn]; bool huan=false,vis[maxn]; queue<int>q; inline void init(){ scanf("%d%d%lf%d%d",&n,&m,&V,&A,&B); for(int i=1; i<=m; i++){ int x,y; db val; scanf("%d%d%lf",&x,&y,&val); go[x].pb(node(y,val)); } } inline void spfa(){ q.push(A); vis[A]=true; dis[A]=V; while(!q.empty()){ int now=q.front(); q.pop(); num[now]++; if(num[now]==n){ huan=true; return; } for(int i=0; i<go[now].size(); i++){ int to=go[now][i].to; db val=go[now][i].val; if(!dis[to] || dis[to]>dis[now]*val){ dis[to]=dis[now]*val; if(!vis[to])vis[to]=true,q.push(to); } } vis[now]=false; } } int main(){ init(); spfa(); if(huan)puts("0"); else printf("%.7lf\n",dis[B]); return 0; } |