| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 518614 | KhoaHo | Robot (JOI21_ho_t4) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/// KoJa
#include <bits/stdc++.h>
using namespace std;
#define task "QG04PAINT"
#define pb push_back
#define SZ(a) (a).begin(), (a).end()
#define SZZ(a, Begin, End) (a) + (Begin), (a) + (Begin) + (End)
#define BIT(a) (1LL << (a))
#define vec vector
#define fi first
#define se second
typedef long long ll;
typedef pair<ll, int> ii;
template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }
void init()
{
freopen(task ".inp", "r", stdin);
freopen(task ".out", "w", stdout);
}
void fastio()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
}
const int N = int(2e5) + 1000;
const ll INF = 1e18;
int n, m;
ll dist[N], best[N], sum[N];
struct Edge
{
int to, c;
ll cost;
Edge(int _to = 0, int _c = 0, ll _cost = 0)
{
to = _to;
c = _c;
cost = _cost;
}
};
vec<Edge> adj[N];
int main()
{
fastio();
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, c;
ll cost;
cin >> u >> v >> c >> cost;
adj[u].pb(Edge(v, c, cost));
adj[v].pb(Edge(u, c, cost));
}
for (int i = 1; i <= n; i++)
dist[i] = INF;
for (int i = 1; i <= m; i++)
{
best[i] = INF;
sum[i] = 0;
}
dist[1] = 0;
priority_queue<ii> q;
q.push(ii(0, 1));
while (!q.empty())
{
int u = q.top().se;
ll du = -q.top().fi;
// cout << u << " " << -du << '\n';
q.pop();
if (du != dist[u])
continue;
for (Edge x : adj[u])
{
sum[x.c] += x.cost;
best[x.c] = min(best[x.c], dist[x.to]);
}
for (Edge x : adj[u])
{
int v = x.to;
int c = x.c;
int cost = x.cost;
ll tmp = min(cost, sum[c] - cost);
if (minimize(dist[v], tmp + du))
q.push(ii(-dist[v], v));
if (minimize(dist[v], best[c] + sum[c] - cost))
q.push(ii(-dist[v], v));
}
for (Edge x : adj[u])
{
sum[x.c] = 0;
best[x.c] = INF;
}
}
if (dist[n] == INF)
dist[n] = -1;
cout << dist[n];
return 0;
}