This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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' ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |