이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;
const int MAX = 2004;
vector<pii> G[MAX];
map<int, ll> CS[MAX];
ll D[MAX][MAX][2], P[MAX], C[MAX];
ll Dijkstra(int N) {
memset(D, 0x3f, sizeof(D));
priority_queue<pair<ll, tuple<ll, ll, ll>>, vector<pair<ll, tuple<ll, ll, ll>>>, greater<pair<ll, tuple<ll, ll, ll>>>> PQ;
PQ.emplace(D[1][0][0] = 0, make_tuple(1, 0, 0));
while (!PQ.empty()) {
auto [cd, p] = PQ.top(); PQ.pop();
ll cur, pen, change;
tie(cur, pen, change) = p;
if (cur == N) return cd;
if (cd > D[cur][pen][change]) continue;
for (auto [next, en] : G[cur]) {
ll c0 = CS[cur][C[en]] - P[en] - (change && C[pen] == C[en] ? P[pen] : 0LL);
ll c1 = P[en];
if (cd + c0 < D[next][en][0]) {
PQ.emplace(D[next][en][0] = cd + c0, make_tuple(next, en, 0));
}
if (cd + c1 < D[next][en][1]) {
PQ.emplace(D[next][en][1] = cd + c1, make_tuple(next, en, 1));
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N, M;
cin >> N >> M;
for (int i = 1; i <= M; ++i) {
ll a, b;
cin >> a >> b >> C[i] >> P[i];
G[a].emplace_back(b, i);
G[b].emplace_back(a, i);
}
for (int i = 1; i <= N; ++i) {
for (auto [_, en] : G[i]) CS[i][C[en]] += P[en];
}
cout << Dijkstra(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... |