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
AC × 45
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