C++14(g++5.4) 解法, 执行用时: 40ms, 内存消耗: 4472K, 提交时间: 2020-10-16 22:03:08

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define maxn 100005
#define ll long long 
using namespace std;

int n,m,s,i,j,k;
int em,e[maxn*2],nx[maxn*2],ls[maxn],ec[maxn*2];
int d[maxn],t,w,vis[maxn];
ll dis[maxn];

void insert(int x,int y,int z){
	em++; e[em]=y; nx[em]=ls[x]; ls[x]=em; ec[em]=z;
	em++; e[em]=x; nx[em]=ls[y]; ls[y]=em; ec[em]=-z;
}

int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(i=1;i<=m;i++) {
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z),z=-z;
		insert(x,y,z);
	}
	t=0,w=1,d[1]=1,vis[1]=1;
	while (t<=w){
		int x=d[++t];
		for(i=ls[x];i;i=nx[i]) if (vis[e[i]]){
			if (dis[x]+ec[i]!=dis[e[i]])
				printf("No Answer\n"),exit(0);
		} else dis[e[i]]=dis[x]+ec[i],d[++w]=e[i],vis[e[i]]=1;
	}
	if (!vis[n]) printf("No Answer\n"),exit(0);
	for(i=2;i<=n;i++) if (vis[i]&&dis[i]>dis[1]) 
		printf("No Answer\n"),exit(0);
	for(i=1;i<n;i++) if (vis[i]&&dis[i]<dis[n])
		printf("No Answer\n"),exit(0);
	printf("%.6Lf",(long double)(dis[1]-dis[n])/s);
}

C++(clang++11) 解法, 执行用时: 161ms, 内存消耗: 7648K, 提交时间: 2021-04-06 22:00:48

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
vector<tuple<int,int>>G[N];
ll h[N];
int dfn[N],dfn_clock,n;
void dfs(int u){
	dfn[u]=++dfn_clock;
	for(auto& i:G[u]){
		int v,w;tie(v,w)=i;
		if(!dfn[v]){
			h[v]=h[u]+w;
			dfs(v);
		}
		else if(h[u]+w!=h[v]){
//			cout<<u<<':'<<h[u]<<'\n';
//			cout<<v<<':'<<h[v]<<'\n';
			puts("No Answer");
			exit(0);
		}
	}
}
int main(){
	int m,I;
	cin>>n>>m>>I;
	while(m--){
		int u,v,w;cin>>u>>v>>w;
		G[u].emplace_back(v,w);
		G[v].emplace_back(u,-w);
	}
	dfs(1);
	if(!dfn[n])goto error;	
	if(*max_element(h+1,h+1+n)!=h[n]||*min_element(h+1,h+1+n)!=h[1]){
		goto error;
	}
	printf("%.6f\n",h[n]/1.0/I);
	return 0;
	error:
		puts("No Answer");
}