Submission #217417

#	Time	Username	Problem	Language	Result	Execution time	Memory
217417		quocnguyen1012	Ceste (COCI17_ceste)	C++14	160 / 160	490 ms	12888 KiB

ceste

#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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16