C++14(g++5.4) 解法, 执行用时: 335ms, 内存消耗: 26584K, 提交时间: 2019-02-10 01:00:44

#include<stdio.h>
#include<queue>
#define fo(i,a,b) for(int i=a;i<=b;i++)
int n,m,xx,yy,zz,be[110000],et,nv;
struct edg{
	int y,ne;
	double z[3];
};
edg e[620000];
inline void add_edge(int x,int y,double z){
	e[++et].y=y;
	e[et].ne=be[x];
	e[et].z[0]=z;
	e[et].z[1]=1/(z-1);
	e[et].z[2]=(z-1)/z;
	be[x]=et;
}
double f[110000][3],oo,te;
bool b[110000][3];
struct nod{
	int u,v;
	double d;
	bool operator <(const nod a)const{
		return d>a.d;
	}
};
std::priority_queue<nod> q;
nod tn;
int main(){
	scanf("%d%d",&n,&m);
	fo(i,1,m){
		scanf("%d%d%d",&xx,&yy,&zz);
		add_edge(xx,yy,zz);
		add_edge(yy,xx,zz);
	}
	oo=1e50;
	fo(i,1,n) fo(j,0,2) f[i][j]=oo;
	f[1][0]=0;
	q.push((nod){1,0,0});
	while (!q.empty()){
		tn=q.top();q.pop();
		if (b[tn.u][tn.v]) continue;
		if (tn.u==n){
			printf("%.3f\n",tn.d);
			return 0;
		}
		b[tn.u][tn.v]=1;
		nv=tn.v+1;if (nv==3) nv=0;
		for(int i=be[tn.u];i;i=e[i].ne){
			int &y=e[i].y;
			te=tn.d+e[i].z[tn.v];
			if (te<f[y][nv]){
				f[y][nv]=te;
				q.push((nod){y,nv,te});
			}
		}
	}
	printf("-1\n");
	return 0;
}

C++ 解法, 执行用时: 634ms, 内存消耗: 49940K, 提交时间: 2021-07-14 11:32:58

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+100;
#define P pair<double,int>
int head[N],nx[N],ed[N];
double val[N];
int cnt;
double d[N];
bool vis[N];
void add(int u,int v,double w) {
	ed[++cnt]=v;
	val[cnt]=w;
	nx[cnt]=head[u];
	head[u]=cnt;
}
priority_queue<P,vector<P>,greater<P>> que;
int main() {
	int n,m;
	cin>>n>>m;
	int u,v;
	double w;
	for(int i=1; i<=m; i++) {
		cin>>u>>v>>w;
		add(u,v+n,w);
		add(v,u+n,w);
		add(u+n,v+n*2,abs(1/(1-w)));
		add(v+n,u+n*2,abs(1/(1-w)));
		add(u+2*n,v,abs((w-1)/w));
		add(v+2*n,u,abs((w-1)/w));
	}
	for(int i=1; i<N; i++) {
		d[i]=0x3f3f3f3f3f3f3f3f;
	}
	d[1]=0;
	que.push(P(0,1));
	while(que.size()) {
		P p=que.top();
		que.pop();
		int u=p.second;
		double w=p.first;
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u]; i; i=nx[i]) {
			if(d[ed[i]]>w+val[i]) {
				d[ed[i]]=w+val[i];
				que.push(P(d[ed[i]],ed[i]));
			}
		}
	}
	double ans=min(d[n],min(d[n*2],d[n*3]));
	if(ans==d[N-1]) {
		cout<<-1<<'\n';
	} else {
		printf("%.3lf\n",ans);
	}
}