제출 #1362760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1362760		opeleklanos	은하철도 (APIO24_train)	C++20	0 / 100	42 ms	12312 KiB

train

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#include "train.h"

#define ll long long
#define INF (ll)1000000000000000000

struct route{
    ll t1;
    ll t0;
    ll from;
    ll dest;
    ll cost;
    ll totalCost;

    const int operator<(route b){
        return t1 < b.t1;
    }
};

vector<vector<ll>> adj;

long long solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y, 
vector<int> A, vector<int> B, vector<int> C, vector<int> L, vector<int> R){

    adj.assign(N, {});

    vector<route> paths;
    for(ll i = 0; i<M; i++){
        adj[X[i]].push_back(i);
        adj[Y[i]].push_back(i);
        paths.push_back({B[i], A[i], X[i], Y[i], C[i], INF});
    }


    for(ll i = 0; i<M; i++){
        if(paths[i].from == 0) paths[i].totalCost = paths[i].cost;
    }

    sort(paths.begin(), paths.end());

    for(ll i = 0; i<M; i++){
        for(auto j : adj[paths[i].from]){
            if(paths[j].dest == paths[i].from && paths[j].t1 <= paths[i].t0){
                paths[i].totalCost = min(paths[i].totalCost, paths[j].totalCost + paths[i].cost);
            }
        }
    }

    ll ans = INF;
    for(ll i = 0; i<M; i++){
        if(paths[i].dest == N-1) ans = min(ans, paths[i].totalCost);
    }

    return ans;
}

• 서브태스크 1: 0 / 5
• 서브태스크 2: 0 / 5
• 서브태스크 3: 0 / 30
• 서브태스크 4: 0 / 60