이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define chmin(a, b) a = min(a,b)
#define chmax(a,b) a = max(a,b)
using T = pair<ll,pii>;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, m, a, b, c, p; cin >> n >> m;
vector<map<int,ll>> trsn(n), sum(n);
vector<ll> dist(n,LLONG_MAX); // self, complement
vector<vector<T>> adj(n);
F0R(i,m) {
cin >> a >> b >> c >> p; a--; b--;
adj[a].pb({b,{c,p}});
adj[b].pb({a,{c,p}});
trsn[a][c] = trsn[b][c] = LLONG_MAX;
sum[a][c] += p; sum[b][c] += p;
}
priority_queue<T,vector<T>,greater<T>> pq; // dist, node, color [1,m], 0 for unspecified color
// t->c, c->c, s->s, c->s->t
dist[0] = 0;
pq.push({0,{0,0}});
//for(auto& x : trsn[0]) {x.s = 0; pq.push({0,{0,x.f}});}
while (pq.size()) {
auto[d,z] = pq.top(); pq.pop();
auto[cur,t] = z;
if ((!t && dist[cur]!=d) || (t && trsn[cur][t]!=d)) {continue;}
/*
self->complement is to any colors such that they are not the
color you came from, but you don't care because if you transition to
the same color you get an unoptimal answer that you will rectify
with transition->complement
so self and complement push to the same thing, so combine them
*/
for (T z : adj[cur]) {
auto[x,y] = z; auto[c,p] = y;
if (!t) { // push to (self, complement), and transition
if (d+p<dist[x]) {pq.push({dist[x]=d+p,{x,0}});}
if (d+sum[cur][c]-p<dist[x]) {pq.push({dist[x]=d+sum[cur][c]-p,{x,0}});}
if (d<trsn[x][c]) {pq.push({trsn[x][c]=d,{x,c}});}
//cout<<dist[2]<<'\n';
} else if (t==c) { // push to complement
//cout << sum[cur][c]-p << '\n';
//cout << x+1 << " " << c << '\n';
if (sum[cur][c]+d-p<dist[x]) {pq.push({dist[x]=sum[cur][c]+d-p,{x,0}});}
}
}
} cout << (dist[n-1]==LLONG_MAX ? -1 : dist[n-1]) << '\n';
//cout<<dist[3]<<'\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... |