| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1337709 | hennessey | 은하철도 (APIO24_train) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define a first
#define b second
#define pb push_back
#define endl '\n'
using vi = vector <int>;
int solve(int32_t n, int32_t m, int32_t w, vi t, vi x, vi y, vi a, vi b, vi c, vi l, vi r) {
vector <vector <vector <int>>> adj(n+1);
for(int i = 0; i < m; i++) adj[x[i]].pb({y[i], a[i], b[i], c[i]});
vector <int> dis(n+2, 1e18); dis[0] = 0;
priority_queue <vector <int>, vector <vector <int>>, greater <vector <int>>> que;
que.push({0, 0, 0});
while(!que.empty()) {
int node = (que.top())[0];
int time = (que.top())[1];
int d = (que.top()[2]);
que.pop();
if(dis[node] != d) continue;
for(auto i:adj[node]) {
if(i[1] < time) continue;
if((i[3]+d) < dis[i[0]]) {
dis[i[0]] = i[3]+d;
que.push({i[0], i[2], dis[i[0]]});
}
}
}
if(dis[n-1] == 1e18) return -1;
return dis[n-1];
}
// signed main() {
// //your code goes here
// ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
// // cout << solve (3, 3, 0, {20, 30, 40}, {0, 1, 0}, {1, 2, 2},
// // {1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19}) << endl;
// return 0;
// }