Submission #1246352
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long int64; const int64 INF = 1LL << 59; typedef pair< int64, int > Pi; struct edge { int64 to, cost; }; int64 N, M, A[100000], B[100000], C[100000], S, T; vector< edge > g[100000]; int64 Dijkstra() { priority_queue< Pi, vector< Pi >, greater< Pi > > que; int64 v[100000]; fill_n(v, 100000, INF); v[S] = 0; que.emplace(0, S); while(!que.empty()) { int64 cost; int idx; tie(cost, idx) = que.top(); que.pop(); if(cost > v[idx]) continue; if(idx == T) return (cost); cost = max(cost, C[idx]); int64 mergin = (cost - C[idx]) % (A[idx] + B[idx]); if(A[idx] <= mergin) cost += A[idx] + B[idx] - mergin; for(auto &e : g[idx]) { if(cost + e.cost < v[e.to]) { v[e.to] = cost + e.cost; que.emplace(v[e.to], e.to); } } } } int main() { cin >> N >> M >> S >> T; --S, --T; for(int i = 0; i < N; i++) { cin >> A[i] >> B[i] >> C[i]; } for(int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; --a, --b; g[a].push_back((edge) {b, c}); g[b].push_back((edge) {a, c}); } cout << Dijkstra() << endl; }
Submission Info
Submission Time | |
---|---|
Task | I - 信号待ち |
User | ei13333 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1241 Byte |
Status | AC |
Exec Time | 243 ms |
Memory | 10880 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00-sample1, 00-sample2, 00-small0, 00-small1, 00-small10, 00-small11, 00-small12, 00-small13, 00-small14, 00-small15, 00-small16, 00-small17, 00-small18, 00-small19, 00-small2, 00-small3, 00-small4, 00-small5, 00-small6, 00-small7, 00-small8, 00-small9, 20-large0, 20-large1, 20-large10, 20-large11, 20-large12, 20-large13, 20-large14, 20-large15, 20-large16, 20-large17, 20-large18, 20-large19, 20-large2, 20-large3, 20-large4, 20-large5, 20-large6, 20-large7, 20-large8, 20-large9, 50-corner00, 50-corner01, 50-corner02 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00-sample1 | AC | 3 ms | 5120 KB |
00-sample2 | AC | 3 ms | 5120 KB |
00-small0 | AC | 3 ms | 5120 KB |
00-small1 | AC | 3 ms | 5120 KB |
00-small10 | AC | 16 ms | 6016 KB |
00-small11 | AC | 10 ms | 5760 KB |
00-small12 | AC | 18 ms | 6016 KB |
00-small13 | AC | 15 ms | 5888 KB |
00-small14 | AC | 12 ms | 5760 KB |
00-small15 | AC | 9 ms | 5632 KB |
00-small16 | AC | 11 ms | 5760 KB |
00-small17 | AC | 11 ms | 5760 KB |
00-small18 | AC | 7 ms | 5376 KB |
00-small19 | AC | 13 ms | 5888 KB |
00-small2 | AC | 3 ms | 5120 KB |
00-small3 | AC | 3 ms | 5120 KB |
00-small4 | AC | 3 ms | 5120 KB |
00-small5 | AC | 3 ms | 5120 KB |
00-small6 | AC | 3 ms | 5120 KB |
00-small7 | AC | 3 ms | 5120 KB |
00-small8 | AC | 3 ms | 5120 KB |
00-small9 | AC | 3 ms | 5120 KB |
20-large0 | AC | 236 ms | 10880 KB |
20-large1 | AC | 237 ms | 10880 KB |
20-large10 | AC | 240 ms | 10880 KB |
20-large11 | AC | 239 ms | 10880 KB |
20-large12 | AC | 239 ms | 10880 KB |
20-large13 | AC | 232 ms | 10880 KB |
20-large14 | AC | 234 ms | 10880 KB |
20-large15 | AC | 232 ms | 10880 KB |
20-large16 | AC | 236 ms | 10880 KB |
20-large17 | AC | 231 ms | 10880 KB |
20-large18 | AC | 243 ms | 10880 KB |
20-large19 | AC | 225 ms | 10880 KB |
20-large2 | AC | 226 ms | 10880 KB |
20-large3 | AC | 232 ms | 10880 KB |
20-large4 | AC | 234 ms | 10880 KB |
20-large5 | AC | 219 ms | 10880 KB |
20-large6 | AC | 227 ms | 10880 KB |
20-large7 | AC | 243 ms | 10880 KB |
20-large8 | AC | 231 ms | 10880 KB |
20-large9 | AC | 233 ms | 10880 KB |
50-corner00 | AC | 208 ms | 10368 KB |
50-corner01 | AC | 176 ms | 10368 KB |
50-corner02 | AC | 148 ms | 10368 KB |