이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
using namespace std;
const int INF = 1e9;
int n, m;
vector<int> a, b, c, p;
vector<vector<int>> g;
vector<map<int, vector<int>>> h;
int solve() {
int ans = -INF;
priority_queue<tuple<int, int, int>> pq;
int dp[n];
dp[0] = 0;
for (int i = 1; i < n; i++) {
dp[i] = -INF;
}
bool vis[n];
memset(vis, 0, sizeof(vis));
pq.push({0, 0, m});
while (not pq.empty()) {
auto [d, u, c_prev] = pq.top();
pq.pop();
if (dp[u] != d) continue;
//cout << d << ' ' << u << ' ' << c_prev << '\n';
if (u == n - 1) ans = max(ans, dp[u]);
if (h[u][c_prev].size() <= 2) {
for (int e : h[u][c_prev]) {
int v = b[e];
if (d <= dp[v]) continue;
dp[v] = d;
pq.push({dp[v], v, c[e]});
}
}
if (vis[u]) continue;
vis[u] = 1;
for (int e : g[u]) {
int v = b[e];
int incur = -(h[u][c[e]].size() > 1);
if (d + incur <= dp[v]) continue;
dp[v] = d + incur;
pq.push({dp[v], v, (incur < 0 ? c[e] : m)});
}
}
return (ans != -INF ? -ans : -1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
m++;
g.resize(n), h.resize(n);
a.resize(2 * m), b.resize(2 * m), c.resize(2 * m), p.resize(2 * m);
for (int i = 0; i < m - 1; i++) {
cin >> a[i] >> b[i] >> c[i] >> p[i];
a[i]--, b[i]--;
p[i] *= -1;
a[i + m] = b[i];
b[i + m] = a[i];
c[i + m] = c[i];
p[i + m] = p[i];
g[a[i]].push_back(i);
g[b[i]].push_back(i + m);
h[a[i]][c[i]].push_back(i);
h[b[i]][c[i + m]].push_back(i + m);
}
cout << solve() << '\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... |