Submission #676530

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <string>
#include <queue>

using namespace std;

int vt[10001];
int vd[10001];
int vrd[10001];
vector<int> vp[10001];
vector<int> vrp[10001];
vector<int> vc[10001];
vector<int> vrc[10001];

int main(){
    int i,j,k,l,n,m;
    int ti;
    
    cin >>n>>m>>ti;
    
    //vector<vector<int>> path;
    
    for (i=1;i<=n;i++){
        cin >> j;
        vt[i]=j;
    }
    
    for (i=0;i<m;i++){
        cin >> j>>k>>l;
        //path.push_back(vector<int>{j,k,l});
        vp[j].push_back(k);
        vrp[k].push_back(j);
        vc[j].push_back(l);
        vrc[k].push_back(l);
    }
    //sort(path.begin(),path.end(),[](vector<int> &v1,vector<int> &v2){return v1[0]!=v2[0]?v1[0]<v2[0]:v1[1]<v2[1];});
    
    queue<vector<int>> qe;
    qe.push(vector<int>{1,0});
    while (!qe.empty()){
        vector<int> e=qe.front();qe.pop();
        i=-1;
        for (int g:vp[e[0]]){
            i++;
            j=e[1]+vc[e[0]][i];
            if (vd[g]!=0 && vd[g]<j) continue;
            vd[g]=j;
            qe.push(vector<int>{g,j});
        }
    }
    
    qe.push(vector<int>{1,0});
    while (!qe.empty()){
        vector<int> e=qe.front();qe.pop();
        i=-1;
        for (int g:vrp[e[0]]){
            i++;
            j=e[1]+vrc[e[0]][i];
            if (vrd[g]!=0 && vrd[g]<j) continue;
            vrd[g]=j;
            qe.push(vector<int>{g,j});
        }
    }
    
    vd[1]=vrd[1]=0;
    //vt-2*vd がmax
    int max=0;
    for (i=1;i<=n;i++){
        k=(ti-vd[i]-vrd[i])*vt[i];
        if (max<k) max=k;
    }
    cout<<max<<endl;
    
    return 0;
}

Submission Info

Judge Result