AtCoder Beginner Contest 035

Submission #676530

Source codeソースコード

#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

Task問題 D - トレジャーハント
User nameユーザ名 舞葉舞
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1750 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt,00_example_03.txt
Subtask1 0 / 50 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 0 / 50 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 5 ms 1152 KB
00_example_02.txt AC 5 ms 1152 KB
00_example_03.txt AC 5 ms 1152 KB
10_rand_01.txt RE
10_rand_02.txt RE
10_rand_03.txt RE
10_rand_04.txt WA
10_rand_05.txt RE
10_rand_06.txt RE
10_rand_07.txt RE
10_rand_08.txt RE
10_rand_09.txt RE
10_rand_10.txt RE
10_rand_12.txt RE
10_rand_13.txt RE
30_max_01.txt RE
30_max_02.txt RE
30_max_03.txt AC 194 ms 4864 KB
30_max_04.txt RE
30_max_05.txt RE
30_max_06.txt RE
40_corner_01.txt RE
40_corner_02.txt RE
40_corner_03.txt RE
40_corner_04.txt RE
50_small_01.txt AC 7 ms 1280 KB
50_small_02.txt AC 6 ms 1152 KB
50_small_03.txt WA
50_small_04.txt AC 6 ms 1152 KB
50_small_05.txt AC 9 ms 1280 KB
50_small_06.txt AC 8 ms 1280 KB
50_small_07.txt WA
50_small_08.txt WA
50_small_09.txt AC 6 ms 1280 KB
50_small_10.txt AC 7 ms 1152 KB
60_hand_01.txt AC 5 ms 1152 KB
60_hand_02.txt WA
60_hand_03.txt WA
60_hand_04.txt WA
70_max_01.txt AC 56 ms 2048 KB
70_max_02.txt AC 56 ms 2048 KB
70_max_03.txt AC 58 ms 2048 KB