oj.uz

Submission #217417

# Submission time Handle Problem Language Result Execution time Memory
217417 2020-03-29T15:11:21 Z quocnguyen1012 Ceste (COCI17_ceste) C++14
160 / 160
 490 ms 12888 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2005;

int U[maxn], V[maxn], T[maxn], C[maxn];
int N, M;
vector<int> adj[maxn];
ll dist[maxn];
int last[maxn];

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> M;
  for(int i = 1; i <= M; ++i){
    cin >> U[i] >> V[i] >> T[i] >> C[i];
    adj[U[i]].eb(i); adj[V[i]].eb(i);
  }
  fill_n(&dist[0], maxn, 1e18);
  fill_n(&last[0], maxn, 1e9);
  priority_queue<pair<ii, int>, vector<pair<ii, int>>, greater<pair<ii, int>>> pq;
  pq.push(mp(mp(0, 0), 1));
  dist[1] = 0; last[1] = 0;
  while(pq.size()){
    auto now = pq.top(); pq.pop();
    int c = now.fi.fi, t = now.fi.se, u = now.se;
    if(last[u] < t) continue;
    last[u] = t;
    dist[u] = min(dist[u], 1ll * t * c);
    for(int id : adj[u]){
      int v = U[id] + V[id] - u;
      if(t + T[id] <= 1e6 && c + C[id] <= 1e6)
        pq.push(mp(mp(c + C[id], t + T[id]), v));
    }
  }
  for(int i = 2; i <= N; ++i) if(dist[i] == 1e18) cout << -1 << '\n'; else cout << dist[i] << '\n' ;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 8 ms 640 KB Output is correct
3 Correct 9 ms 640 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1404 KB Output is correct
2 Correct 60 ms 2172 KB Output is correct
3 Correct 77 ms 2328 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 2160 KB Output is correct
2 Correct 490 ms 12888 KB Output is correct
3 Correct 10 ms 768 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 960 KB Output is correct
2 Correct 307 ms 6756 KB Output is correct
3 Correct 17 ms 640 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 1012 KB Output is correct
2 Correct 238 ms 2320 KB Output is correct
3 Correct 208 ms 2160 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 2304 KB Output is correct
2 Correct 215 ms 2160 KB Output is correct
3 Correct 285 ms 2160 KB Output is correct