Submission #3006348


Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <math.h>
#define MOD 1000000007
#define INFTY (1<<20)
typedef long long ll;
using namespace std;
int n,m,t;
int A[100001];
vector<pair<int,int>> v[100001];
vector<pair<int,int>> g[100001];
ll d1[100001];
ll d2[100001];


void dijkstra1(){
  priority_queue<pair<int,int>> PQ;
  //int d[n];
  for(int i=0;i<n;i++) d1[i]=INFTY;

  d1[0]=0;
  PQ.push(make_pair(0,0));

  while(!PQ.empty()){
    pair<int,int> f=PQ.top();
    PQ.pop();
    int u=f.second;

    if(d1[u]<f.first*(-1)) continue;

    for(int j=0;j<v[u].size();j++){
      int x=v[u][j].first;
      if(d1[x]>d1[u]+v[u][j].second){
        d1[x]=d1[u]+v[u][j].second;
        PQ.push(make_pair(d1[x]*(-1),x));
      }
    }
  }
  //ll ans=0;
  /*for(int i=0;i<n;i++){
    if(d[i]*2>=t) continue;
    ans=max(ans,((ll)t-d[i]*2)*A[i]);
    //cout<<i<<" "<<(d[i]==INFTY?-1:d[i])<<endl;
  }
  cout<<ans<<endl;*/
}

void dijkstra2(){
  priority_queue<pair<int,int>> PQ;
  //int d[n];
  for(int i=0;i<n;i++) d2[i]=INFTY;

  d2[0]=0;
  PQ.push(make_pair(0,0));

  while(!PQ.empty()){
    pair<int,int> f=PQ.top();
    PQ.pop();
    int u=f.second;

    if(d2[u]<f.first*(-1)) continue;

    for(int j=0;j<g[u].size();j++){
      int x=g[u][j].first;
      if(d2[x]>d2[u]+g[u][j].second){
        d2[x]=d2[u]+g[u][j].second;
        PQ.push(make_pair(d2[x]*(-1),x));
      }
    }
  }
  ll ans=0;
  for(int i=0;i<n;i++){
    if(d1[i]+d2[i]>=t) continue;
    ans=max(ans,(t-d1[i]-d2[i])*A[i]);
    //cout<<i<<" "<<(d[i]==INFTY?-1:d[i])<<endl;
  }
  cout<<ans<<endl;
}

int main(){
  //int n,m,t;
  cin>>n>>m>>t;
  //ll A[n]={};
  for(int i=0;i<n;i++) cin>>A[i];
  //vector<pair<int,int>> v[n];
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c;
    a--;
    b--;
    v[a].push_back(make_pair(b,c));
    g[b].push_back(make_pair(a,c));
  }
  dijkstra1();
  dijkstra2();
  return 0;
}

Submission Info

Submission Time
Task D - トレジャーハント
User snow39
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2042 Byte
Status WA
Exec Time 123 ms
Memory 13184 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 50 0 / 50
Status
AC × 3
AC × 19
WA × 1
AC × 35
WA × 7
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
Subtask1 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 10_rand_12.txt, 10_rand_13.txt, 30_max_01.txt, 30_max_02.txt, 30_max_03.txt, 30_max_04.txt, 30_max_05.txt, 30_max_06.txt, 40_corner_01.txt, 40_corner_02.txt, 40_corner_03.txt, 40_corner_04.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 3 ms 4992 KB
00_example_02.txt AC 3 ms 4992 KB
00_example_03.txt AC 3 ms 4992 KB
10_rand_01.txt AC 8 ms 5376 KB
10_rand_02.txt AC 29 ms 6272 KB
10_rand_03.txt AC 11 ms 5504 KB
10_rand_04.txt AC 5 ms 5120 KB
10_rand_05.txt WA 12 ms 5632 KB
10_rand_06.txt WA 11 ms 5760 KB
10_rand_07.txt WA 16 ms 6144 KB
10_rand_08.txt AC 8 ms 5376 KB
10_rand_09.txt AC 14 ms 5888 KB
10_rand_10.txt AC 5 ms 5120 KB
10_rand_12.txt AC 50 ms 6784 KB
10_rand_13.txt AC 46 ms 6656 KB
30_max_01.txt AC 103 ms 8564 KB
30_max_02.txt AC 117 ms 9360 KB
30_max_03.txt AC 86 ms 8100 KB
30_max_04.txt AC 119 ms 11136 KB
30_max_05.txt AC 123 ms 11136 KB
30_max_06.txt AC 122 ms 11136 KB
40_corner_01.txt AC 105 ms 13184 KB
40_corner_02.txt WA 106 ms 13184 KB
40_corner_03.txt WA 109 ms 13184 KB
40_corner_04.txt WA 113 ms 13184 KB
50_small_01.txt AC 4 ms 4992 KB
50_small_02.txt AC 3 ms 4992 KB
50_small_03.txt AC 3 ms 4992 KB
50_small_04.txt AC 3 ms 4992 KB
50_small_05.txt AC 5 ms 4992 KB
50_small_06.txt AC 4 ms 4992 KB
50_small_07.txt AC 3 ms 4992 KB
50_small_08.txt AC 2 ms 4992 KB
50_small_09.txt AC 3 ms 4992 KB
50_small_10.txt AC 3 ms 4992 KB
60_hand_01.txt WA 2 ms 4992 KB
60_hand_02.txt AC 3 ms 4992 KB
60_hand_03.txt AC 3 ms 4992 KB
60_hand_04.txt AC 2 ms 4992 KB
70_max_01.txt AC 28 ms 5888 KB
70_max_02.txt AC 28 ms 5888 KB
70_max_03.txt AC 28 ms 5888 KB