C++14(g++5.4) 解法, 执行用时: 33ms, 内存消耗: 5360K, 提交时间: 2020-09-07 20:06:36

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn=100010;
typedef long long ll;
ll n,m,c[maxn],T,cur,h[maxn],nxt[maxn],p[maxn],w[maxn],u,v,t;
ll dist[maxn],siz[maxn],ans;
bool tf[maxn];
struct node
{
    ll id,v;
    bool operator<(node x)const{return v>x.v;}
};
priority_queue<node>q;
vector<int>g[10010];
void add_edge(ll u,ll v,ll t)
{
    cur++;
    nxt[cur]=h[u];
    h[u]=cur;
    p[cur]=v;
    w[cur]=t;
}
bool f[maxn];
void dfs(int x)
{
    siz[x]=c[x];f[x]=true;
    for(vector<int>::iterator it=g[x].begin();it!=g[x].end();it++)
    if(!f[*it])dfs(*it),siz[x]+=siz[*it];
    ans=max(ans,siz[x]*(dist[x]-T));
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&T);
    for(int i=1;i<=n;i++)scanf("%lld",c+i);
    while(m--)scanf("%lld%lld%lld",&u,&v,&t),add_edge(u,v,t),add_edge(v,u,t);
    q.push({1,0});
    while(!q.empty())
    {
        node x=q.top();q.pop();
        if(tf[x.id])continue;
        tf[x.id]=true;dist[x.id]=x.v;
        for(int j=h[x.id];j;j=nxt[j])q.push({p[j],x.v+w[j]});
    }
    memset(tf,0,sizeof tf);
    for(int i=1;i<=n;i++)for(int j=h[i];j;j=nxt[j])
    if(dist[p[j]]==dist[i]+w[j]&&!tf[p[j]])tf[p[j]]=true,
    g[i].push_back(p[j]),g[p[j]].push_back(i);
    dfs(1);
    printf("%lld\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 31ms, 内存消耗: 4600K, 提交时间: 2020-09-07 20:58:34

#include<bits/stdc++.h> 
#define int long long
using namespace std;
const int N=1e4+1;
int n,m,t,ans,a[N];
int dis[N],vis[N],tot[N],d[N];
vector<int>v[N],w[N],tr[N],trw[N];
void spfa()
{
	queue<int>q;
	int n1,n2;
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	vis[1]=1;
	q.push(1);
	while(!q.empty())
	{
		n1=q.front();
		q.pop();
		for(int i=0;i<v[n1].size();i++)
		{
			n2=v[n1][i];
			if(dis[n2]>dis[n1]+w[n1][i])
			{
				dis[n2]=dis[n1]+w[n1][i];
				if(vis[n2]==0)
				q.push(n2),vis[n2]=1;
			}
		}
		vis[n1]=0;
	}
}
void dfs(int x)
{
	int n1;
	tot[x]=a[x];
	for(int i=0;i<tr[x].size();i++)
	{
		n1=tr[x][i];
		d[n1]=d[x]+trw[x][i];
		dfs(n1);
		tot[x]+=tot[n1];
	}
}
signed main()
{
	int x,y,z;
	scanf("%lld%lld%lld",&n,&m,&t);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		v[x].push_back(y);
		v[y].push_back(x);
		w[x].push_back(z);
		w[y].push_back(z);
	}
	spfa();
	for(int i=2;i<=n;i++)
	{
		y=n+1;
		for(int j=0;j<v[i].size();j++)
		{
			x=v[i][j];
			if(dis[x]+w[i][j]==dis[i])
			if(y>x)
			y=x,z=w[i][j];
		}
		tr[y].push_back(i);
		trw[y].push_back(z);
	}
	dfs(1);
	for(int i=1;i<=n;i++)
	ans=max(ans,tot[i]*(d[i]-t));
	printf("%lld",ans);
	return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 330ms, 内存消耗: 31176K, 提交时间: 2020-09-07 20:49:42

#!/usr/bin/env python3
#
# Shortcut
#
import sys, os
from heapq import heappush, heappop, heappushpop, heapify

def read_ints(): return list(map(int, input().split()))

N, M, T = read_ints()
c = read_ints()
g = [[] for _ in range(N)]
for _ in range(M):
	u, v, t = read_ints()
	g[u - 1].append((v - 1, t))
	g[v - 1].append((u - 1, t))

parent, dist = [-1] * N, [-1] * N
dist[0] = 0
q = [(0, 0)]
while q:
	d, u = heappop(q)
	for v, w in g[u]:
		if dist[v] < 0 or d + w < dist[v]:
			dist[v], parent[v] = d + w, u
			heappush(q, (d + w, v))

for u in range(N):
	if parent[u] < 0: continue
	for v, w in g[u]:
		if dist[v] + w == dist[u] and v < parent[u]: parent[u] = v

d = [0] * N
for u in range(N):
	x = c[u]
	while parent[u] >= 0:
		d[u] += x
		u = parent[u]
ans = 0
for u in range(1, N):
	ans = max(ans, d[u] * (dist[u] - T))

print(ans)