C++14(g++5.4) 解法, 执行用时: 836ms, 内存消耗: 17400K, 提交时间: 2019-04-01 14:24:39

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int x[2000005];
int y[2000005];
int r[2000005];
LL dis[2000005];
int main()
{
    int n,m;
    LL s;
    cin>>n>>m>>s;
    for(int i=0;i<m;i++)
        cin>>x[i]>>y[i]>>r[i];
    int flag=1;
    while(flag) {
        flag=0;
        for(int i=0;i<m;i++) {
            if(dis[x[i]]+r[i]>dis[y[i]]) {
                flag=1;
                dis[y[i]]=dis[x[i]]+r[i];
            }
        }
    }
    LL sum=0;
    for(int i=1;i<=n;i++)
        sum+=dis[i];
    if(sum==0) {
        puts("-1");
    }
    else if(sum>s) {
        puts("0");
    }
    else {
        cout<< s/sum;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 537ms, 内存消耗: 15204K, 提交时间: 2020-02-27 00:03:58

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,m,s,x[600100],y[600100],r[600100],a[200100],tol=0;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		scanf("%lld %lld %lld",&x[i],&y[i],&r[i]);
		if((a[x[i]]+r[i])>a[y[i]])
		{
			a[y[i]]=a[x[i]]+r[i];
		}
	}
	for(int i=1;i<=100;i++)
	{
		for(int  j=1;j<=m;j++)
		{
			if((a[x[j]]+r[j])>a[y[j]])
			{
				a[y[j]]=a[x[j]]+r[j];
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		tol+=a[i];
	}
	if(tol==0)
	{
		cout<<"-1";
	}
	else
	{
		cout<<s/tol;
	}
	return 0;
}