爆零求救
查看原帖
爆零求救
221522
张睿洲Richard楼主2021/7/23 17:10
#include<bits/stdc++.h>
using namespace std;
struct node{
	int v,w;
	node(){}
	node(int vv,int ww){
		v=vv;
		w=ww;
	}
};
vector<node>g[110000];
int n,m,s,d[110000],t;
set<pair<int,int> >min_heap;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(node(v,w));
		g[v].push_back(node(u,w));
	}
	memset(d,0x3f,sizeof d);
	cin>>s>>t;
	d[s]=0;
	min_heap.insert(make_pair(0,s));
	while(min_heap.size()){
		int mind=min_heap.begin()->first,v=min_heap.begin()->second;
		min_heap.erase(min_heap.begin());
		for(int i=0;i<g[v].size();i++){
			if(d[g[v][i].v]>d[v]+g[v][i].w){
				min_heap.erase(make_pair(d[g[v][i].v],g[v][i].v));
				d[g[v][i].v]=d[v]+g[v][i].w;
				min_heap.insert(make_pair(d[g[v][i].v],g[v][i].v));
			}
		}
	}
	double sum=1.0+d[t]/100*1.0,ans;
	ans=100.0*sum;
	printf("%.8f\n",ans);
	return 0;
}
2021/7/23 17:10
加载中...