提出 #777621

---

ソースコード 拡げる

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#define INF 1000000007
#define int long long
#define ll long long
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
namespace Dikstra{
    struct Node{
        int pos,prev;
		ll cost;
        vector<int> to;
        vector<ll> to_cost;
        static bool Graeter(const Node& a,const Node& b){return a.cost>b.cost;}
        static bool Less(const Node& a,const Node& b){return a.cost<b.cost;}
    };
    class Greater{public: bool operator()(const Node& a,const Node& b){return a.cost>b.cost;}};
    class Less   {public: bool operator()(const Node& a,const Node& b){return a.cost<b.cost;}};
    class Dikstra{
    public:
        int n;
        vector<Node> nodes;
        Dikstra(void){}
        Dikstra(int n_){n=n_; nodes.resize(n);init();}
        void init(){REP(i,n)nodes[i].pos=i,nodes[i].cost=INF,nodes[i].prev=INF;}
        void addEdge(int x,int y,ll cost_){
            nodes[x].to.push_back(y);
            nodes[x].to_cost.push_back(cost_);
        }
        vector<ll> culCost(int start){
            nodes[start].cost=0;
            priority_queue<Node,vector<Node>,Greater> Q;
            Q.push(nodes[start]);
            while(!Q.empty()){
                Node current = Q.top();Q.pop();
                REP(i,current.to.size()){
                    Node& next = nodes[current.to[i]];
                    if (next.cost > current.cost + current.to_cost[i]){
                        next.cost = current.cost + current.to_cost[i];
                        next.prev = current.pos;
                        Q.push(next);
                    }
                }
            }
            vector<ll> res(n);
            REP(i,n){res[i]=nodes[i].cost;}
            return res;
        }
    };
}


signed main(){
	int N,M;
	ll T;
	cin>>N>>M>>T;
	vector<ll> A(N,0);
	Dikstra::Dikstra dik(N);
	Dikstra::Dikstra rdik(N);

	REP(i,N) cin>>A[i];
	REP(i,M){
		int a,b;ll c;cin>>a>>b>>c;a--;b--;
		dik.addEdge(a,b,c);
		rdik.addEdge(b,a,c);
	}
	vector<ll> res =dik.culCost(0);
	vector<ll> rres=rdik.culCost(0);
	ll ma=0;
	REP(i,N){
// 		cout<<res[i] << " "<<rres[i]<<endl;
 		if(T<res[i]+rres[i]) continue;
		ma = max(ma,A[i]*(T-res[i]-rres[i]));
	}
	cout<<ma<<endl;
	return 0;
}

提出情報

ジャッジ結果