求dalao解答,为什么要建双向边QAQ?
查看原帖
求dalao解答,为什么要建双向边QAQ?
637073
wujingfey楼主2022/11/19 16:50
#include<bits/stdc++.h>
#define pdi pair<double,int>
#define pid pair<int,double>
using namespace std;
const int N=2e3+10;
const double INF=1e9;
int n,m,vis[N],st,ed;
double dis[N];
vector<pid> e[N];
void dijkstra(int root){
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[root]=100;
	priority_queue<pdi,vector<pdi>,greater<pdi> > pq;
	pq.push({100,root});
	while(!pq.empty()){
		int u=pq.top().second;
		pq.pop();
		if(vis[u]==1) continue;
		vis[u]=1;
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].first;
			double c=e[u][i].second;
			if(dis[u]/(1-c/100)<dis[v]){
				dis[v]=dis[u]/(1-c/100);
				pq.push({dis[v],v});
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,b;
		double c;
		scanf("%d%d%lf",&a,&b,&c);
		e[b].push_back({a,c});
		e[a].push_back({b,c});
	}
	scanf("%d%d",&st,&ed);
	dijkstra(ed);
	printf("%.8lf",dis[st]);
	return 0;
}

蒟蒻反向建边,已知end是100,那就从后往前求最小的st。照理说走回来就多收手续费了,肯定不优啊。但建单向边的我听取WA声一片了

2022/11/19 16:50
加载中...