結果
| 問題 | No.3561 Collect KCPC |
| コンテスト | |
| ユーザー |
 jastaway
|
| 提出日時 | 2026-05-28 14:16:42 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 2,456 ms / 6,000 ms |
| コード長 | 7,820 bytes |
| 記録 | |
| コンパイル時間 | 393 ms |
| コンパイル使用メモリ | 85,636 KB |
| 実行使用メモリ | 245,696 KB |
| 最終ジャッジ日時 | 2026-05-29 18:49:47 |
| 合計ジャッジ時間 | 38,305 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_1 |
| 純コード判定待ち |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| 部分点1 | 10 % | AC * 15 |
| 部分点2 | 20 % | AC * 15 |
| 部分点3 | 20 % | AC * 13 |
| 部分点4 | 50 % | AC * 51 |
| 合計 | 100 点 |
ソースコード
"""
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
using p2 = pair<ll, int>;
template<class T, class U> bool chmin(T& a, U b) { return a > b ? a = b, 1 : 0; }
int main(int argc, char* argv[]) {
int N, M; cin >> N >> M;
vector<vector<pair<int, ll>>> G(N), rG(N);
for(int i = 0; i < M; i++)
{
int u, v; ll c;
cin >> u >> v >> c;
u--; v--;
G[u].emplace_back(v, c);
rG[v].emplace_back(u, c);
}
string S; cin >> S;
vector<ll> d1(N, INF);
{
priority_queue<p2, vector<p2>, greater<p2>> pq;
d1[0] = 0;
pq.emplace(0, 0);
while(!pq.empty())
{
auto [d, n] = pq.top(); pq.pop();
if(d1[n] < d) continue;
for(auto [e, c] : G[n])
{
if(chmin(d1[e], d1[n] + c)) pq.emplace(d1[e], e);
}
}
}
vector<ll> dK(N, INF);
{
priority_queue<p2, vector<p2>, greater<p2>> pq;
for(int i = 0; i < N; i++) if(S[i] == 'K')
{
dK[i] = d1[i];
pq.emplace(d1[i], i);
}
while(!pq.empty())
{
auto [d, n] = pq.top(); pq.pop();
if(dK[n] < d) continue;
for(auto [e, c] : G[n])
{
if(chmin(dK[e], dK[n] + c)) pq.emplace(dK[e], e);
}
}
}
vector<pair<p2, p2>> dP1(N, {p2{INF, -1}, p2{INF, -1}}), dP2(N, {p2{INF, -1}, p2{INF, -1}});
{
priority_queue<pair<p2, int>, vector<pair<p2, int>>, greater<pair<p2, int>>> pq;
for(int i = 0; i < N; i++) if(S[i] == 'C' && dK[i] < INF)
{
dP1[i].first = {dK[i], i};
pq.emplace(p2{dK[i], i}, i);
}
while(!pq.empty())
{
auto [di, n] = pq.top(); pq.pop();
auto [d, i] = di;
if(dP1[n].second.first < d) continue;
for(auto [e, c] : G[n])
{
if(dP1[e].first.first > d + c)
{
if(dP1[e].first.second != i) dP1[e].second = dP1[e].first;
dP1[e].first = {d + c, i};
pq.emplace(p2{d + c, i}, e);
}
else if(dP1[e].second.first > d + c && dP1[e].first.second != i)
{
dP1[e].second = {d + c, i};
pq.emplace(p2{d + c, i}, e);
}
}
}
for(int i = 0; i < N; i++) if(S[i] == 'C')
{
dP2[i].first = {0, i};
pq.emplace(p2{0, i}, i);
}
while(!pq.empty())
{
auto [di, n] = pq.top(); pq.pop();
auto [d, i] = di;
if(dP2[n].second.first < d) continue;
for(auto [e, c] : rG[n])
{
if(dP2[e].first.first > d + c)
{
if(dP2[e].first.second != i) dP2[e].second = dP2[e].first;
dP2[e].first = {d + c, i};
pq.emplace(p2{d + c, i}, e);
}
else if(dP2[e].second.first > d + c && dP2[e].first.second != i)
{
dP2[e].second = {d + c, i};
pq.emplace(p2{d + c, i}, e);
}
}
}
}
ll ans = INF;
for(int i = 0; i < N; i++) if(S[i] == 'P')
{
auto [pi1, pi2] = dP1[i];
auto [p1, i1] = pi1;
auto [p2, i2] = pi2;
auto [qj1, qj2] = dP2[i];
auto [q1, j1] = qj1;
auto [q2, j2] = qj2;
if(i1 != j1) chmin(ans, p1 + q1);
if(i1 != j2) chmin(ans, p1 + q2);
if(i2 != j1) chmin(ans, p2 + q1);
if(i2 != j2) chmin(ans, p2 + q2);
}
if(ans == INF) cout << -1 << endl;
else cout << ans << endl;
}
"""
import sys
import heapq
def solve():
# Fast I/O is critical for translating C++ code without causing TLE in Python
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
M = int(input_data[1])
G = [[] for _ in range(N)]
rG = [[] for _ in range(N)]
idx = 2
for _ in range(M):
u = int(input_data[idx]) - 1
v = int(input_data[idx+1]) - 1
c = int(input_data[idx+2])
G[u].append((v, c))
rG[v].append((u, c))
idx += 3
S = input_data[idx]
INF = 1 << 60
# ----------------------------------------------------
# Dijkstra 1
# ----------------------------------------------------
d1 = [INF] * N
d1[0] = 0
pq = [(0, 0)]
while pq:
d, n = heapq.heappop(pq)
if d1[n] < d:
continue
for e, c in G[n]:
if d1[e] > d1[n] + c:
d1[e] = d1[n] + c
heapq.heappush(pq, (d1[e], e))
# ----------------------------------------------------
# Dijkstra 2
# ----------------------------------------------------
dK = [INF] * N
pq = []
for i in range(N):
if S[i] == 'K':
dK[i] = d1[i]
heapq.heappush(pq, (d1[i], i))
while pq:
d, n = heapq.heappop(pq)
if dK[n] < d:
continue
for e, c in G[n]:
if dK[e] > dK[n] + c:
dK[e] = dK[n] + c
heapq.heappush(pq, (dK[e], e))
# ----------------------------------------------------
# Dijkstra 3 (dP1 & dP2)
# ----------------------------------------------------
dP1 = [[[INF, -1], [INF, -1]] for _ in range(N)]
dP2 = [[[INF, -1], [INF, -1]] for _ in range(N)]
pq = []
for i in range(N):
if S[i] == 'C' and dK[i] < INF:
dP1[i][0] = [dK[i], i]
# Equivalent to pair<p2, int> structure for tie-breaking: (dist, source, node)
heapq.heappush(pq, (dK[i], i, i))
while pq:
d, i, n = heapq.heappop(pq)
if dP1[n][1][0] < d:
continue
for e, c in G[n]:
if dP1[e][0][0] > d + c:
if dP1[e][0][1] != i:
dP1[e][1] = list(dP1[e][0])
dP1[e][0] = [d + c, i]
heapq.heappush(pq, (d + c, i, e))
elif dP1[e][1][0] > d + c and dP1[e][0][1] != i:
dP1[e][1] = [d + c, i]
heapq.heappush(pq, (d + c, i, e))
pq = []
for i in range(N):
if S[i] == 'C':
dP2[i][0] = [0, i]
heapq.heappush(pq, (0, i, i))
while pq:
d, i, n = heapq.heappop(pq)
if dP2[n][1][0] < d:
continue
for e, c in rG[n]:
if dP2[e][0][0] > d + c:
if dP2[e][0][1] != i:
dP2[e][1] = list(dP2[e][0])
dP2[e][0] = [d + c, i]
heapq.heappush(pq, (d + c, i, e))
elif dP2[e][1][0] > d + c and dP2[e][0][1] != i:
dP2[e][1] = [d + c, i]
heapq.heappush(pq, (d + c, i, e))
# ----------------------------------------------------
# Calculate Answer
# ----------------------------------------------------
ans = INF
for i in range(N):
if S[i] == 'P':
p1, i1 = dP1[i][0]
p2, i2 = dP1[i][1]
q1, j1 = dP2[i][0]
q2, j2 = dP2[i][1]
if i1 != j1:
if ans > p1 + q1: ans = p1 + q1
if i1 != j2:
if ans > p1 + q2: ans = p1 + q2
if i2 != j1:
if ans > p2 + q1: ans = p2 + q1
if i2 != j2:
if ans > p2 + q2: ans = p2 + q2
if ans == INF:
print(-1)
else:
print(ans)
if __name__ == '__main__':
solve()