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 PB push_back
#define sz(x) ((int)x.size())
#define ft first
#define sd second
using namespace std;
typedef long long ll;
const int N = 110;
const int MX = 10010;
const int oo = 2e9;
const ll OO = 1e18;
const int md = int(1e9) + 7;
vector<int> g[N];
int n, m, ans[N], f[N][MX], A[N], B[N], C[N], T[N];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m;
for (int i = 0; i < m; i++){
cin >> A[i] >> B[i] >> T[i] >> C[i];
A[i]--; B[i]--;
g[A[i]].PB(i);
g[B[i]].PB(i);
}
for (int i = 0; i < n; i++){
ans[i] = oo;
for (int j = 0; j < MX; j++)
f[i][j] = oo;
}
f[0][0] = 0;
for (int tim = 1; tim < MX; tim++){
for (int v = 0; v < n; v++) {
for (int id : g[v]){
int u = (A[id] == v ? B[id] : A[id]);
int ot = tim - T[id];
if (ot < 0) continue;
if (f[u][ot] == oo) continue;
f[v][tim] = min(f[v][tim], f[u][ot] + C[id]);
}
if (f[v][tim] == oo) continue;
ans[v] = min(ans[v], f[v][tim] * tim);
}
}
for (int i = 1; i < n; i++)
cout << (ans[i] == oo ? -1 : ans[i]) << '\n';
return 0;
}
# | 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... |