蒟蒻p1576 SPFA零分求助
  • 板块P1576 最小花费
  • 楼主_luo_gu
  • 当前回复13
  • 已保存回复13
  • 发布时间2023/10/3 15:23
  • 上次更新2023/11/2 16:08:30
查看原帖
蒟蒻p1576 SPFA零分求助
950927
_luo_gu楼主2023/10/3 15:23

感谢大佬sto

#include <bits/stdc++.h>
#define int long long
using namespace std ;
struct Edge{
	double v ;
	double w ;//转账的税(整数 
};
vector <Edge> edge[2010] ;
queue <int> que ;
int n , m , A , B ;
double dis[2010]  ;//到达当前点的税的总数
bool vis[2010] ;//记录点是否来到过 


void spfa( int x ){
	dis[x] = 1 ;
	vis[x] = true ;
	que.push(x);
	int u ;
	int v ;
	while( que.empty() == false ){ 
		u = que.front() ;
		que.pop() ;
//		vis[u] = false ;
		for( int i = 0 ; i < edge[u].size() ; i ++ ){
			v = edge[u][i].v ;
			if( dis[v] < dis[u] *(edge[u][i].w+1)){
				dis[v] = dis[u] *(edge[u][i].w+1) ;
				cout << "Test: "<<edge[u][i].w<<endl;
				if( vis[v] == false ){
					que.push(v);
					vis[v] = true ;
				}
			}
		}
		cout << "test" << endl;
	}
}


signed main(){
	cin >> n >> m ;
	int x , y ;
	double z ;
	for( int i = 1 ; i <= m ; i ++ ){
		cin >> x >> y >> z ;
		Edge xx ;
		xx.v = y ;
		xx.w = z/100 ;
		edge[x].push_back(xx);
		xx.v = x ;
		edge[y].push_back(xx);
	}
	memset( dis , 0 , sizeof(dis));
	memset( vis , false , sizeof(vis));
	cin >> A >> B ;
	spfa(A);
	printf("%.8llf",100*dis[B]);
	return 0 ;
}

感谢大佬!好人一生平安sto

2023/10/3 15:23
加载中...