最短経路で価値の最大化

[tipstar0125]

https://atcoder.jp/contests/abc286/tasks/abc286_e

[tipstar0125]

BFS解法

• 距離が短くなったら、価値を更新
• 距離が等しいときは、価値が大きくなったら更新

input! {
    N: usize,
    A: [usize; N],
    S: [Chars; N],
    Q: usize,
    UV: [(Usize1, Usize1); Q]
}

let mut G = vec![vec![]; N];
for i in 0..N {
    for j in 0..N {
        if S[i][j] == 'Y' {
            G[i].push(j);
        }
    }
}
let INF = 1_usize << 60;

let mut point = vec![vec![0_usize; N]; N];
let mut dist = vec![vec![INF; N]; N];
for i in 0..N {
    let mut Q = VecDeque::new();
    point[i][i] = A[i];
    dist[i][i] = 0;
    Q.push_back(i);
    while !Q.is_empty() {
        let pos = Q.pop_front().unwrap();
        for &next in &G[pos] {
            if dist[i][next] > dist[i][pos] + 1 {
                point[i][next] = point[i][pos] + A[next];
                dist[i][next] = dist[i][pos] + 1;
                Q.push_back(next);
            } else if dist[i][next] == dist[i][pos] + 1 && point[i][next] < point[i][pos] + A[next] {
                point[i][next] = point[i][pos] + A[next];
                Q.push_back(next);
            }
        }
    }
}
for &(start, stop) in &UV {
    if dist[start][stop] == INF {
        println!("Impossible");
    } else {
        println!("{} {}", dist[start][stop], point[start][stop]);
    }
}

[tipstar0125]

ワーシャルフロイド解法

• ある始点からの最短経路とその過程で得られる価値の最大を求める
• 最後に始点の価値を足す

N=int(input())
A=list(map(int,input().split()))
S=[input() for _ in range(N)]
Q=int(input())

G=[[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i==j:continue
        if S[i][j]=="Y":G[i].append(j)

INF=int(1e18)
dist=[[INF for _ in range(N)] for _ in range(N)]
score=[[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j in G[i]:
        dist[i][j]=1
        score[i][j]=A[j]

for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][k]+dist[k][j]<dist[i][j]:
                dist[i][j]=dist[i][k]+dist[k][j]
                score[i][j]=score[i][k]+score[k][j]
            if dist[i][k]+dist[k][j]==dist[i][j] and score[i][k]+score[k][j]>score[i][j]:
                score[i][j]=score[i][k]+score[k][j]

for _ in range(Q):
    u,v=list(map(int,input().split()))
    u-=1
    v-=1
    if dist[u][v]==INF:print("Impossible")
    else:print(dist[u][v], score[u][v]+A[u])