oj.uz

Submission #217416

# Submission time Handle Problem Language Result Execution time Memory
217416 2020-03-29T15:10:47 Z quocnguyen1012 Ceste (COCI17_ceste) C++14
48 / 160
 266 ms 2172 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; 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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct

Subtask #3
16.0 / 16.0

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

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1404 KB Output is correct
2 Correct 63 ms 2172 KB Output is correct
3 Correct 76 ms 2172 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 2156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 1040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 266 ms 1140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 2160 KB Output isn't correct
2 Halted 0 ms 0 KB -