全WA求助
查看原帖
全WA求助
668869
Fire_flame楼主2022/4/15 20:17
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
int n,m,s,t;
struct node{
	int to;
	double w;
};
vector<node>g[MAXN];
double dis[MAXN];
void SPFA(){
	queue<int>q;
	q.push(t);
	for(int i=1;i<=n;i++)dis[i]=1000000000.0;
	dis[t]=100.0;
	while(!q.empty()){
		int h=q.front();q.pop();
		for(int i=0;i<g[h].size();i++){
			int v=g[h][i].to;
			if(dis[v]>dis[h]*(1.0+g[h][i].w)){
				dis[v]=dis[h]*(1.0+g[h][i].w);
				q.push(v);
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		double x;
		scanf("%d%d%lf",&u,&v,&x);
		g[v].push_back((node){u,x/100.0});
	}
	scanf("%d%d",&s,&t);
	SPFA();
	printf("%.8lf",dis[s]);
	return 0;
}
2022/4/15 20:17
加载中...